Submission #105705

#TimeUsernameProblemLanguageResultExecution timeMemory
105705Pro_ktmr허수아비 (JOI14_scarecrows)C++14
100 / 100
2554 ms50752 KiB
#include"bits/stdc++.h" using namespace std; #define LL long long #define REP(i, n) for(int (i)=0; (i)<(n); (i)++) #define PB push_back #define MP make_pair #define all(x) x.begin(),x.end() #define int long long //RSQ セグメント木 struct SegmentTree{ private: int n; vector<int> nodes; const int DEFAULT = 0; public: void init(int N){ //初期化する O(N) nodes.clear(); n = 1; while(n < N) n *= 2; n = 2 * n -1; for(int i=0; i<n; i++) nodes.push_back(DEFAULT); } void update(int i, int x){ //値を変更する O(log N) i += n / 2; nodes[i] = x; while(i > 0){ i = (i-1)/2; //親の取得は(i-1)/2 nodes[i] = nodes[i*2+1] + nodes[i*2+2]; //子の取得はi*2+1,i*2+2 } } int sum(int a, int b, int k=0, int l=0, int r=-1){ //[a,b)の最小値を求める O(log N) if(r == -1) r = n/2+1; if(r <= a || b <= l) return DEFAULT; //交差する場合 if(a <= l && r <= b) return nodes[k]; //完全に含む場合 int valueL = sum(a, b, k*2+1, l, (l+r)/2); int valueR = sum(a, b, k*2+2, (l+r)/2, r); return valueL + valueR; } }; int N; pair<int,int> point[200000]; //数学と同じ座標の取り方→xとyの大小関係一致 vector<int> zaatuX,zaatuY; LL ans = 0; void DevideConquer(int l, int r){ if(r-l == 1) return; int m = (l+r)/2; vector<int> zaatu; for(int i=l; i<r; i++) zaatu.PB(point[i].second); sort(zaatu.begin(), zaatu.end()); set<int> st1,st2; vector<pair<pair<int,int>,int>> kukan; for(int i=m-1; i>=l; i--){ int y = lower_bound(zaatu.begin(), zaatu.end(), point[i].second) - zaatu.begin(); auto itr = st1.lower_bound(y); if(itr == st1.end()) kukan.PB(MP(MP(y,N),0)); else kukan.PB(MP(MP(y,*itr),0)); st1.insert(y); } for(int i=m; i<r; i++){ int y = lower_bound(zaatu.begin(), zaatu.end(), point[i].second) - zaatu.begin(); auto itr = st2.lower_bound(y); if(itr == st2.begin()) kukan.PB(MP(MP(0,y),1)); else{ itr--; kukan.PB(MP(MP(*itr,y),1)); } st2.insert(y); } sort(kukan.begin(), kukan.end()); SegmentTree rsq; //右サイドの上端 rsq.init(r-l); for(int i=0; i<kukan.size(); i++){ if(kukan[i].second == 0){ ans += rsq.sum(kukan[i].first.first, kukan[i].first.second); } else{ rsq.update(kukan[i].first.second, 1); } } DevideConquer(l, m); DevideConquer(m, r); } signed main(){ scanf("%d", &N); for(int i=0; i<N; i++){ scanf("%d%d", &point[i].first, &point[i].second); zaatuX.PB(point[i].first); zaatuY.PB(point[i].second); } sort(zaatuX.begin(), zaatuX.end()); sort(zaatuY.begin(), zaatuY.end()); for(int i=0; i<N; i++){ point[i].first = lower_bound(zaatuX.begin(), zaatuX.end(), point[i].first) - zaatuX.begin(); point[i].second = lower_bound(zaatuY.begin(), zaatuY.end(), point[i].second) - zaatuY.begin(); } sort(point, point+N); // DevideConquer(0, N); printf("%lld\n", ans); return 0; }

Compilation message (stderr)

scarecrows.cpp: In function 'void DevideConquer(long long int, long long int)':
scarecrows.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<kukan.size(); i++){
               ~^~~~~~~~~~~~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:95:16: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d", &N);
              ~~^
scarecrows.cpp:97:50: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d%d", &point[i].first, &point[i].second);
                 ~~~~~~~~~~~~~~~                  ^
scarecrows.cpp:97:50: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
scarecrows.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
scarecrows.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &point[i].first, &point[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...