Submission #508586

#TimeUsernameProblemLanguageResultExecution timeMemory
50858679brueMatryoshka (JOI16_matryoshka)C++14
0 / 100
1 ms460 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Query{ int x, y, idx; Query(){} Query(int x, int y, int idx): x(x), y(y), idx(idx){} bool operator<(const Query &r)const{ return y!=r.y ? y<r.y : x<r.x; } }; struct Fenwick { int tree[1000002]; int n = 1000000; void add(int x, int v){ assert(x<=n); while(x<=n){ tree[x] += v; x += x&-x; } } int sum(int x){ assert(x<=n); int ret=0; while(x){ ret += tree[x]; x -= x&-x; } return ret; } } tree; int n, q; pair<int, int> arr[200002]; Query query[200002]; set<pair<int, int> > st; int ans[200002]; void renumber(){ vector<int> vec; for(int i=1; i<=n; i++) vec.push_back(arr[i].first); for(int i=1; i<=q; i++) vec.push_back(query[i].x); sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end())); for(int i=1; i<=n; i++) arr[i].first = lower_bound(vec.begin(), vec.end(), arr[i].first) - vec.begin() + 1; for(int i=1; i<=q; i++) query[i].x = lower_bound(vec.begin(), vec.end(), query[i].x) - vec.begin() + 1; } int main(){ scanf("%d %d", &n, &q); for(int i=1; i<=n; i++){ scanf("%d %d", &arr[i].first, &arr[i].second); } for(int i=1; i<=q; i++){ scanf("%d %d", &query[i].x, &query[i].y); query[i].idx = i; } renumber(); sort(arr+1, arr+n+1, [&](pair<int, int> x, pair<int, int> y){ return x.second != y.second ? x.second < y.second : x.first > y.first; }); sort(query+1, query+q+1); int pnt = 1; for(int i=1; i<=q; i++){ while(pnt <= n && query[i].y >= arr[pnt].second){ tree.add(arr[pnt].first, 1); auto it = st.lower_bound(make_pair(arr[pnt].first, -1)); if(it == st.begin()){ st.insert(make_pair(arr[pnt].first, pnt)); pnt++; continue; } --it; tree.add(it->first, -1); st.insert(make_pair(arr[pnt].first, pnt)); st.erase(it); ++pnt; } ans[query[i].idx] = tree.sum(1000000) - tree.sum(query[i].x - 1); } for(int i=1; i<=q; i++) printf("%d\n", ans[i]); }

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
matryoshka.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d %d", &arr[i].first, &arr[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d %d", &query[i].x, &query[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...