Submission #929237

#TimeUsernameProblemLanguageResultExecution timeMemory
929237ono_de206Inspections (NOI23_inspections)C++14
100 / 100
1681 ms70932 KiB
#include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define in insert #define all(x) x.begin(),x.end() #define pb push_back #define eb emplace_back #define ff first #define ss second #define int long long typedef long long ll; typedef vector<int> vi; typedef set<int> si; typedef multiset<int> msi; typedef pair<int, int> pii; typedef vector<pii> vpii; // typedef pair<int, int> P; template<typename T, typename U> ostream & operator << (ostream &out, const pair<T, U> &c) { out << c.first << ' ' << c.second; return out; } template<typename T> ostream & operator << (ostream &out, vector<T> &v) { const int sz = v.size(); for (int i = 0; i < sz; i++) { if (i) out << ' '; out << v[i]; } return out; } template<typename T> istream & operator >> (istream &in, vector<T> &v) { for (T &x : v) in >> x; return in; } template<typename T, typename U> istream & operator >> (istream &in, pair<T, U> &c) { in >> c.first; in >> c.second; return in; } template<typename T> void mxx(T &a, T b){if(b > a) a = b;} template<typename T> void mnn(T &a, T b){if(b < a) a = b;} const int mxn = 2e5 + 10, MXLOG = 22, mod = 1e9 + 7, P = 1181, D = 1523, N = 2500; const long long inf = 2e18 + 10; int l[mxn], r[mxn], qry[mxn], pre[mxn]; map<int, int> mp; vector<int> add[mxn], rem[mxn]; set<int> s; int now, n; int get(int le, int ri) { return pre[ri - 1] - pre[le] + r[le] - l[ri]; } void insert(int id) { int le = -1, ri = -1; auto it = s.lower_bound(id); if(it != s.end()) ri = *it; if(it != s.begin()) le = *prev(it); if(le != -1 && ri != -1) { int x = get(le, ri); mp[-x] -= (n - now + 1); } if(le != -1) { int x = get(le, id); mp[-x] += (n - now + 1); } if(ri != -1) { int x = get(id, ri); mp[-x] += (n - now + 1); } s.in(id); } void erase(int id) { s.erase(id); int le = -1, ri = -1; auto it = s.lower_bound(id); if(it != s.end()) ri = *it; if(it != s.begin()) le = *prev(it); if(le != -1 && ri != -1) { int x = get(le, ri); mp[-x] += (n - now + 1); } if(le != -1) { int x = get(le, id); mp[-x] -= (n - now + 1); } if(ri != -1) { int x = get(id, ri); mp[-x] -= (n - now + 1); } } void go() { int m, q; cin >> n >> m >> q; for(int i = 1; i <= m; i++) { cin >> l[i] >> r[i]; add[l[i]].eb(i); rem[r[i] + 1].eb(i); } for(int i = 1; i <= m; i++) { pre[i] = pre[i - 1] + (r[i] - l[i] + 1); } for(int i = 1; i <= n; i++) { now = i; for(int id : rem[i]) { erase(id); } for(int id : add[i]) { insert(id); } } for(int i = 1; i <= q; i++) { cin >> qry[i]; mp[-qry[i]] += 0; } int ls = 0; for(auto &it : mp) { it.ss += ls; ls = it.ss; } for(int i = 1; i <= q; i++) { cout << mp[-qry[i]] << ' '; } cout << endl; } signed main() { fast; int t = 1; // cin >> t; while(t--) { go(); } 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...