2010-06-18
SRM473 Div1 Medium(500): RightTriangle
|に該当する場所が空いていない時の処理が最悪ケースでTLE
の場所をインクリメントしておいて、あとで均せばO(points+places)で行けるじゃん
- それだけ。passed system test
typedef long long ll; #define sz(a) int((a).size()) #define pb push_back #define FOR(var,from,to) for(int var=(from);var<=(to);var++) #define rep(var,n) for(int var=0;var<(n);var++) #define all(c) (c).begin(),(c).end() #define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++) #define found(s,e) ((s).find(e)!=(s).end()) typedef long long ll; class RightTriangle { public: long long triangleCount(int places, int points, int a, int b, int c) { if(places & 1) return 0LL; vector<int> cnt(places,0); for(ll n=0; n<points; ++n) { ll ix = n*n*a + n*b + c; cnt[ix % places]++; } int r=0; rep(ix,places*2){ int j=ix%places; cnt[j]+=r; r=max(cnt[j]-1,0); cnt[j]=min(1,cnt[j]); } vector<int> acc(places*2+1,0); acc[0]=0; rep(n,places) acc[n+1]=acc[n]+cnt[n]; int ap=acc[places]; rep(n,places+1) acc[places+n]=ap+acc[n]; ll accum=0LL; int h=places/2; rep(n,places){ int nh = (n + h) % places; if(cnt[n] && cnt[nh]) { accum += acc[n+h] - acc[n+1]; } } return accum; } };
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100618