naoya_t@topcoder

SRM473 Div1 Medium(500): RightTriangle

14:33 |

• に該当する場所が空いていない時の処理が最悪ケースで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;
  }
};