Submission #130122

#TimeUsernameProblemLanguageResultExecution timeMemory
130122choikiwonWorst Reporter 2 (JOI16_worst_reporter2)C++17
0 / 100
11 ms9724 KiB
#include<bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int MN = 200010; int N; vector<int> V[MN], X[MN]; priority_queue<int> freeV; multiset<int> freeX; int la[MN]; int main() { std::ios::sync_with_stdio(false); cin >> N; for(int i = 0; i < N; i++) { int a, b; cin >> a >> b; V[--a].push_back(b); } for(int i = 0; i < N; i++) { int c, d; cin >> c >> d; X[--c].push_back(d); } int ans = 0; for(int i = 0; i < N; i++) { sort(V[i].begin(), V[i].end()); sort(X[i].begin(), X[i].end()); vector<int> chk(V[i].size(), 0); vector<int> tmp; int pos = (int)X[i].size() - 1; for(int j = (int)V[i].size() - 1; j >= 0; j--) { if(pos >= 0 && V[i][j] <= X[i][pos]) { pos--; continue; } freeV.push(V[i][j]); chk[j] = 1; } for(int j = 0; j < V[i].size(); j++) if(!chk[j]) tmp.push_back(V[i][j]); V[i] = tmp; if(V[i].size() == 0) { for(int j = 0; j < X[i].size(); j++) { freeX.insert(X[i][j]); } la[i] = -1; continue; } chk = vector<int>(X[i].size(), 0); pos = 0; for(int j = 0; j < V[i].size(); j++) { while(pos < X[i].size() && X[i][pos] < V[i][j]) pos++; chk[pos] = 1; pos++; } tmp.clear(); for(int j = 0; j < X[i].size(); j++) { if(chk[j]) tmp.push_back(X[i][j]); else freeX.insert(X[i][j]); } X[i] = tmp; la[i] = (int)V[i].size() - 1; } ans += freeV.size(); while(!freeV.empty()) { int v = freeV.top(); freeV.pop(); auto it = freeX.lower_bound(v); if(it != freeX.end()) { freeX.erase(it); continue; } ans++; int mn = 1e9; int p = -1; for(int i = 0; i < N; i++) { while(la[i] >= 0 && V[i][ la[i] ] >= v) la[i]--; if(la[i] >= 0 && X[i][ la[i] ] >= v) { int tmp = 1e9; for(int j = la[i]; j >= 0; j--) { if(j == 0 || X[i][j - 1] < V[i][j]) { tmp = V[i][j]; break; } } if(mn > tmp) { mn = tmp; p = i; } } } for(int i = la[p]; i >= 0; i--) { if(i == 0 || X[p][i - 1] < V[p][i]) { freeV.push(V[p][i]); V[p][i] = v; break; } else swap(v, V[p][i]); } freeX.insert(v); } cout << ans; }

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < V[i].size(); j++) if(!chk[j]) tmp.push_back(V[i][j]);
                        ~~^~~~~~~~~~~~~
worst_reporter2.cpp:49:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < X[i].size(); j++) {
                            ~~^~~~~~~~~~~~~
worst_reporter2.cpp:59:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < V[i].size(); j++) {
                        ~~^~~~~~~~~~~~~
worst_reporter2.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(pos < X[i].size() && X[i][pos] < V[i][j]) pos++;
                   ~~~~^~~~~~~~~~~~~
worst_reporter2.cpp:66:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < X[i].size(); j++) {
                        ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...