Submission #833029

#TimeUsernameProblemLanguageResultExecution timeMemory
833029LiudasInspections (NOI23_inspections)C++17
100 / 100
815 ms43332 KiB
#include <iostream> #include <vector> #include <set> #include <map> #include <climits> #include <algorithm> #define int long long using namespace std; struct seg{ int l; int r; int time; bool operator<(const seg &a)const{ if(l == a.l){ return r < a.r; } return l < a.l; } }; // need : inter left // got : cover all inter right map<int, int> vals; set<seg> in; vector<seg> to_err, to_add; void compare(seg &a, seg &b){ if(b.l < a.l){ seg c = {b.l, a.l-1, b.time}; to_add.push_back(c); b.time += a.l - b.l; b.l = a.l; } if(b.r > a.r){ seg c = {a.r + 1, b.r, b.time + a.r - b.l + 1}; to_add.push_back(c); b.r = a.r; } } signed main(){ int N, Q, M; cin >> N >> M >> Q; vector<seg> arr(M); int day = 0; for(int i = 0; i < M; i ++){ int a, b; cin >> a >> b; arr[i] = {a,b,day}; day += b-a+1; } seg tt = {INT_MIN, INT_MIN, INT_MIN}; in.insert(tt); for(int i = 0; i < M; i ++){ seg a = arr[i]; seg t = a; t.l = t.r; t.r = INT_MAX; auto p = --in.upper_bound(t); while((*p).r >= a.l){ seg b = *p; p--; //cout << " A " << a.l << " " << a.r << " " << a.time << endl; //cout << " B " << b.l << " " << b.r << " " << b.time << endl; to_err.push_back(b); compare(a, b); //cout << "AD A " << a.l << " " << a.r << " " << a.time << endl; //cout << "AD B " << b.l << " " << b.r << " " << b.time << endl; int lmax = max(a.l, b.l); int rmin = min(a.r, b.r); int td = b.l - a.l; vals[a.time + td - b.time - 1] += rmin-lmax+1; } for(auto j : to_err){ in.erase(j); } to_err.clear(); for(auto j : to_add){ in.insert(j); } to_add.clear(); in.insert(a); } for(auto i : in){ //cout << "liko " << i.l << " " << i.r << " " << i.time << endl; } vector<pair<int, int>> pref; for(auto[l, r] : vals){ pref.push_back({l, r}); //cout << l <<" " << r << endl; } pref.push_back({(int)1e16, 0ll}); for(int i = (int)pref.size()-2; i > -1; i --){ pref[i].second += pref[i+1].second; } for(auto[l, r] : pref){ //cout << "P " << l << " " << r << endl; } for(int i = 0; i < Q; i ++){ int q; cin >> q; cout << (*lower_bound(pref.begin(), pref.end(), make_pair(q, 0ll))).second << " "; } cout << endl; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:82:14: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   82 |     for(auto i : in){
      |              ^
Main.cpp:94:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   94 |     for(auto[l, r] : pref){
      |             ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...