Submission #933320

#TimeUsernameProblemLanguageResultExecution timeMemory
933320browntoadInspections (NOI23_inspections)C++14
100 / 100
263 ms25772 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define REP1(i, n) FOR(i, 1, n+1) #define pii pair<int, int> #define ppi pair<pii, int> #define ALL(x) (x).begin(), (x).end() #define SZ(x) (int)((x).size()) #define f first #define s second #define pb push_back #define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define endl '\n' const ll maxn = 1e6+5; const ll inf = 1ll<<60; const ll mod = 1e9+7; int n, m, q; vector<pii> tag; // lazy tag to modify suffix set<ppi> st; set<ppi> ::iterator rep(set<ppi> ::iterator it, int L, int R, int v){ ppi cur = (*it); int l = cur.f.f; int r = cur.f.s; //cout<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<cur.s<<' '<<v<<endl; if (r < L || l > R) return next(it); if (l < L && r > R){ tag.pb({v-(cur.s+L-l)-1, R-L+1}); st.insert({{l, L-1}, cur.s}); st.insert({{R+1, r}, cur.s+R+1-l}); return st.erase(it); } if (l < L){ //cout<<"toad"<<endl; tag.pb({v-(cur.s+L-l)-1, r-L+1}); st.insert({{l, L-1}, cur.s}); return st.erase(it); } if (r > R){ tag.pb({v-(cur.s-(l-L))-1, R-l+1}); st.insert({{R+1, r}, cur.s+R+1-l}); return st.erase(it); } tag.pb({v-(cur.s-(l-L))-1, r-l+1}); return st.erase(it); } signed main(){ IOS(); cin>>n>>m>>q; int cval = 0; REP(i, m){ int L, R; cin>>L>>R; if (SZ(st) > 0){ auto tt = st.lower_bound({{L+1, 0}, 0}); if (tt != st.begin()){ tt = prev(tt); } while(tt != st.end() && (*tt).f.f <= R){ tt = rep(tt, L, R, cval); } } st.insert({{L, R}, cval}); cval += R-L+1; } sort(ALL(tag), greater<pii> ()); vector<pii> quer(q); REP(i, q){ cin>>quer[i].f; quer[i].s = i; } vector<int> ans(q); sort(ALL(quer), greater<pii> ()); int ptr = 0, woo = 0; REP(i, q){ while(ptr < SZ(tag) && tag[ptr].f >= quer[i].f){ woo += tag[ptr].s; ptr++; } ans[quer[i].s] = woo; } REP(i, q) cout<<ans[i]<<' '; cout<<endl; } /* 5 3 7 1 3 3 5 2 3 bruh 4 minutes debug */
#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...