Submission #124625

#TimeUsernameProblemLanguageResultExecution timeMemory
124625mirbek01Examination (JOI19_examination)C++11
100 / 100
309 ms10184 KiB
# include <bits/stdc++.h> using namespace std; const int N = 2e5 + 3; struct st{ int x, y, z; int a, b, c; }a[N], b[N]; int n, m, ans[N], fen[3][N]; vector <int> v1, v2, v3; void upd(int tp, int r){ for(; r < N; r |= r + 1) fen[tp][r] ++; } int get(int tp, int l){ int ret = 0; for(; l > 0; l = (l & (l + 1)) - 1) ret += fen[tp][l]; return ret; } int main(){ scanf("%d %d", &n, &m); for(int i = 1; i <= n; i ++){ scanf("%d %d", &a[i].a, &a[i].b); a[i].c = a[i].a + a[i].b; v1.push_back(a[i].a); v2.push_back(a[i].b); v3.push_back(a[i].c); a[i].x = i; } for(int i = 1; i <= m; i ++){ scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].z); b[i].z = max(b[i].z, b[i].x + b[i].y); v1.push_back(b[i].x); v2.push_back(b[i].y); v3.push_back(b[i].z); } sort(v1.begin(), v1.end()); v1.resize(unique(v1.begin(), v1.end()) - v1.begin()); sort(v2.begin(), v2.end()); v2.resize(unique(v2.begin(), v2.end()) - v2.begin()); sort(v3.begin(), v3.end()); v3.resize(unique(v3.begin(), v3.end()) - v3.begin()); for(int i = 1; i <= n; i ++){ a[i].a = lower_bound(v1.begin(), v1.end(), a[i].a) - v1.begin() + 1; a[i].b = lower_bound(v2.begin(), v2.end(), a[i].b) - v2.begin() + 1; a[i].c = lower_bound(v3.begin(), v3.end(), a[i].c) - v3.begin() + 1; } for(int i = 1; i <= m; i ++){ b[i].x = lower_bound(v1.begin(), v1.end(), b[i].x) - v1.begin() + 1; b[i].y = lower_bound(v2.begin(), v2.end(), b[i].y) - v2.begin() + 1; b[i].z = lower_bound(v3.begin(), v3.end(), b[i].z) - v3.begin() + 1; b[i].a = i; } sort(a + 1, a + n + 1, [](st a, st b){ return a.c > b.c;}); sort(b + 1, b + m + 1, [](st a, st b){ return a.z > b.z;}); int pt = 0; for(int i = 1; i <= m; i ++){ while(pt + 1 <= n && a[pt + 1].c >= b[i].z){ pt ++; upd(1, a[pt].a); upd(2, a[pt].b); } ans[ b[i].a ] = pt - get(1, b[i].x - 1) - get(2, b[i].y - 1); } for(int i = 1; i <= m; i ++) printf("%d\n", ans[i]); }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a[i].a, &a[i].b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...