제출 #105720

#제출 시각아이디문제언어결과실행 시간메모리
105720Pro_ktmrWorst Reporter 2 (JOI16_worst_reporter2)C++14
100 / 100
1096 ms51560 KiB
#include"bits/stdc++.h" using namespace std; #define MP(a,b) make_pair(a,b) //RAQ RMQ セグメント木 struct SegmentTree{ private: int n; vector<long long> nodes,lazy; public: void init(int N){ //初期化する O(N) nodes.clear(); lazy.clear(); n = 1; while(n < N) n *= 2; n = 2 * n -1; for(int i=0; i<n; i++){ nodes.push_back(0); lazy.push_back(0); } } void eval(int k, int l, int r){ //遅延評価を行う if(lazy[k] == 0) return; nodes[k] += lazy[k]; if(r-l > 1){ lazy[2*k+1] += lazy[k]; lazy[2*k+2] += lazy[k]; } lazy[k] = 0; } void add(int a, int b, long long x, int k=0, int l=0, int r=-1){ //区間に対して値を加算する O(log N) if(r == -1) r = n/2+1; eval(k, l, r); if(r <= a || b <= l) return; //交差する場合 if(a <= l && r <= b){ //完全に含む場合 lazy[k] += x; eval(k, l, r); } else{ add(a, b, x, 2*k+1, l, (l+r)/2); add(a, b, x, 2*k+2, (l+r)/2, r); nodes[k] = min(nodes[2*k+1], nodes[2*k+2]); } } long long minimum(int a, int b, int k=0, int l=0, int r=-1){ //[a,b)の最小値を求める O(log N) //cout << a << " " << b << " " << k << " " << l << " " << r << endl; if(r == -1) r = n/2+1; if(r <= a || b <= l) return LLONG_MAX; //交差する場合 eval(k, l, r); if(a <= l && r <= b) return nodes[k]; //完全に含む場合 long long valueL = minimum(a, b, k*2+1, l, (l+r)/2); long long valueR = minimum(a, b, k*2+2, (l+r)/2, r); return min(valueL, valueR); } void print(){ cout << "nodes" << endl; int sp = n; int nx = 0; for(int i=0; i<nodes.size(); i++){ cout << nodes[i]; for(int j=0; j<sp; j++) cout << " "; if(i == nx){ nx = nx*2+2; sp /= 2; cout << endl; } } cout << "lazy" << endl; sp = n; nx = 0; for(int i=0; i<lazy.size(); i++){ cout << lazy[i]; for(int j=0; j<sp; j++) cout << " "; if(i == nx){ nx = nx*2+2; sp /= 2; cout << endl; } } cout << endl; } }; int N; int A[200000],B[200000],C[200000],D[200000]; set<pair<int,int>> nokori[200000]; bool already1[200000] = {}; bool already2[200000] = {}; vector<int> all,diff; SegmentTree st; int main(){ scanf("%d", &N); for(int i=0; i<N; i++){ scanf("%d%d", A+i, B+i); A[i]--; all.push_back(B[i]); nokori[A[i]].insert(MP(B[i],i)); } for(int i=0; i<N; i++){ scanf("%d%d", C+i, D+i); C[i]--; all.push_back(D[i]); } sort(all.begin(), all.end()); // vector<int> moto,ato; for(int i=N-1; i>=0; i--){ if(!already1[i]) moto.push_back(B[i]); } for(int i=N-1; i>=0; i--){ if(!already2[i]) ato.push_back(D[i]); } int idx1 = 0; int idx2 = 0; for(int i=0; i<all.size(); i++){ while(idx1 < moto.size() && moto[idx1] <= all[i]) idx1++; while(idx2 < ato.size() && ato[idx2] <= all[i]) idx2++; diff.push_back(idx1-idx2); } st.init(all.size()); for(int i=0; i<all.size(); i++) st.add(i, i+1, diff[i]); // int ans = N; for(int i=N-1; i>=0; i--){ auto itr = nokori[C[i]].upper_bound(MP(D[i]+1, -1)); int tmp; if(itr == nokori[C[i]].begin()) tmp = -1; else{ itr--; tmp = itr->second; nokori[C[i]].erase(itr); already1[tmp] = false; already2[i] = false; st.add(lower_bound(all.begin(), all.end(), B[tmp])-all.begin(), all.size(), -1); st.add(lower_bound(all.begin(), all.end(), D[i])-all.begin(), all.size(), +1); } if(st.minimum(0,all.size()) >= 0 && tmp >= 0){ ans--; } else{ if(tmp >= 0){ nokori[C[i]].insert(MP(B[tmp],tmp)); already1[tmp] = false; already2[i] = false; st.add(lower_bound(all.begin(), all.end(), B[tmp])-all.begin(), all.size(), +1); st.add(lower_bound(all.begin(), all.end(), D[i])-all.begin(), all.size(), -1); } } } printf("%d\n", ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

worst_reporter2.cpp: In member function 'void SegmentTree::print()':
worst_reporter2.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<nodes.size(); i++){
                ~^~~~~~~~~~~~~
worst_reporter2.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<lazy.size(); i++){
                ~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<all.size(); i++){
               ~^~~~~~~~~~~
worst_reporter2.cpp:119:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx1 < moto.size() && moto[idx1] <= all[i]) idx1++;
         ~~~~~^~~~~~~~~~~~~
worst_reporter2.cpp:120:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx2 < ato.size() && ato[idx2] <= all[i]) idx2++;
         ~~~~~^~~~~~~~~~~~
worst_reporter2.cpp:125:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<all.size(); i++) st.add(i, i+1, diff[i]);
               ~^~~~~~~~~~~
worst_reporter2.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", A+i, B+i);
   ~~~~~^~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", C+i, D+i);
   ~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...