Submission #102485

#TimeUsernameProblemLanguageResultExecution timeMemory
102485FutymyCloneExamination (JOI19_examination)C++14
2 / 100
3107 ms232768 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int n, q, ans[N], cnt = 0; map <int, int> bit[N], compress; vector <int> vecm, veci; struct data { int math, infor, sum; bool operator < (const data &rhs) const { return sum > rhs.sum; } } a[N]; struct Query { int a, b, c, id; bool operator < (const Query &rhs) const { return c > rhs.c; } } queries[N]; void update (int x, int y, int val) { for (int i = x; i > 0; i -= i & -i) { for (int j = y; j > 0; j -= j & -j) { bit[i][j] += val; } } } int get_value (int x, int y) { int ans = 0; for (int i = x; i < N; i += i & -i) { for (int j = y; j < N; j += j & -j) { ans += bit[i][j]; } } return ans; } int main(){ scanf("%d %d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d %d", &a[i].math, &a[i].infor); a[i].sum = a[i].math + a[i].infor; vecm.push_back(a[i].math); veci.push_back(a[i].infor); } for (int i = 1; i <= q; i++) { scanf("%d %d %d", &queries[i].a, &queries[i].b, &queries[i].c); queries[i].id = i; vecm.push_back(queries[i].a); veci.push_back(queries[i].b); } sort(a + 1, a + n + 1); sort(queries + 1, queries + q + 1); sort(vecm.begin(), vecm.end()); sort(veci.begin(), veci.end()); //Compress coordinate compress[vecm[0]] = ++cnt; for (int i = 1; i < vecm.size(); i++) if (vecm[i] > vecm[i - 1]) compress[vecm[i]] = ++cnt; for (int i = 1; i <= n; i++) a[i].math = compress[a[i].math]; for (int i = 1; i <= q; i++) queries[i].a = compress[queries[i].a]; cnt = 0; compress.clear(); compress[veci[0]] = ++cnt; for (int i = 1; i < veci.size(); i++) if (veci[i] > veci[i - 1]) compress[veci[i]] = ++cnt; for (int i = 1; i <= n; i++) a[i].infor = compress[a[i].infor]; for (int i = 1; i <= q; i++) queries[i].b = compress[queries[i].b]; // int ptr = 1; for (int i = 1; i <= q; i++) { while (ptr <= n && a[ptr].sum >= queries[i].c) { update(a[ptr].math, a[ptr].infor, 1); ptr++; } ans[queries[i].id] = get_value(queries[i].a, queries[i].b); } for (int i = 1; i <= q; i++) printf("%d\n", ans[i]); return 0; }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < vecm.size(); i++) if (vecm[i] > vecm[i - 1]) compress[vecm[i]] = ++cnt;
                     ~~^~~~~~~~~~~~~
examination.cpp:73:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < veci.size(); i++) if (veci[i] > veci[i - 1]) compress[veci[i]] = ++cnt;
                     ~~^~~~~~~~~~~~~
examination.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a[i].math, &a[i].infor);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &queries[i].a, &queries[i].b, &queries[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...