Submission #1205590

#TimeUsernameProblemLanguageResultExecution timeMemory
1205590biankInspections (NOI23_inspections)C++20
0 / 100
118 ms8624 KiB
#include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<int(n);i++) #define forsn(i,s,n) for(int i=int(s);i<int(n);i++) #define dforn(i,n) for(int i=int(n)-1;i>=0;i--) #define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--) #define fst first #define snd second #define pb push_back #define eb emplace_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() typedef long long ll; typedef vector<ll> vll; typedef vector<int> vi; typedef pair<int,int> ii; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m,q; cin>>n>>m>>q; set<tuple<int,int,ll>> ranges; vector<pair<ll,ll>> v; ll x=0; forn(i,m){ int l,r; cin>>l>>r; --l,--r; auto it=ranges.lower_bound({l+1,0,0LL}); if(it!=begin(ranges)){ auto[s,e,y]=*prev(it); if(s<=l&&l<=e){ ll first=y+l-s; v.eb(x-first-1,min(r,e)-l+1); ranges.erase(prev(it)); if(s<l) ranges.emplace(s,l-1,y); if(r<e) ranges.emplace(r+1,e,y+r+1-s); } } it=ranges.lower_bound({l+1,0,0LL}); while(it!=end(ranges)){ auto[s,e,y]=*it; if(s>r) break; ll first=x+s-l; v.eb(first-y-1,min(r,e)-s+1); it=ranges.erase(it); if(r<e){ ranges.emplace(r+1,e,y+r+1-s); break; } } ranges.emplace(l,r,x); x+=r-l+1; } sort(all(v)); forn(i,sz(v)-1) v[i+1].snd+=v[i].snd; forn(i,q){ ll s; cin>>s; int lo=-1,hi=sz(v); while(hi-lo>1){ int mid=(lo+hi)/2; if(v[mid].fst>=s) hi=mid; else lo=mid; } ll res=v[sz(v)-1].snd-(lo==-1?0:v[lo].snd); cout<<res<<' '; } cout<<'\n'; return 0; }
#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...