#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
int n = 1, m = 1, k, q, say1 = 1, say2, seg1[N], sol1[N], sag1[N], seg2[N], sol2[N], sag2[N], ans[N];
pair < int , ii > a[N];
pair < ii , ii > b[N];
int ver(int k){return seg1[k] = (!seg1[k])?++say2:seg1[k];}
int solver1(int k){return sol1[k] = (!sol1[k])?++say1:sol1[k];}
int sagver1(int k){return sag1[k] = (!sag1[k])?++say1:sag1[k];}
int solver2(int k){return sol2[k] = (!sol2[k])?++say2:sol2[k];}
int sagver2(int k){return sag2[k] = (!sag2[k])?++say2:sag2[k];}
void up2(int k, int bas, int son, int x){
if(bas == son){
seg2[k]++;
return;
}
if(x <= orta)
up2(solver2(k), bas, orta, x);
else
up2(sagver2(k), orta + 1, son, x);
seg2[k] = seg2[sol2[k]] + seg2[sag2[k]];
}
void up1(int k, int bas, int son, int x, int y){
if(bas == son){
up2(ver(k), 1, m, y);
// cout << bas << " " << son << " " << ver(k) << " a " << y << " artti" << endl;
return;
}
if(x <= orta)
up1(solver1(k), bas, orta, x, y);
else
up1(sagver1(k), orta + 1, son, x, y);
// cout << bas << " " << son << " " << ver(k) << " a " << y << " artti" << endl;
up2(ver(k), 1, m, y);
}
int qu2(int k, int bas, int son, int x){
if(!k or son < x)
return 0;
if(bas >= x)
return seg2[k];
return qu2(sol2[k], bas, orta, x) + qu2(sag2[k], orta + 1, son, x);
}
int qu1(int k, int bas, int son, int x, int y){
if(!k or son < x)
return 0;
if(bas >= x){
// cout << bas << " " << son << " " << seg1[k] << " " << y << " = " << qu2(seg1[k], 1, m, y) << endl;
return qu2(seg1[k], 1, m, y);
}
return qu1(sol1[k], bas, orta, x, y) + qu1(sag1[k], orta + 1, son, x, y);
}
int main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d %d",&k ,&q);
for(int i = 1; i <= k; i++){
scanf("%d %d",&a[i].nd.st ,&a[i].nd.nd);
a[i].st = a[i].nd.st + a[i].nd.nd;
n = max(n, a[i].nd.st);
m = max(m, a[i].nd.nd);
}
n++;m++;
sort(a + 1, a + k + 1);
for(int i = 1; i <= q; i++){
scanf("%d %d %d" ,&b[i].nd.st ,&b[i].nd.nd,&b[i].st.st);
b[i].st.nd = i;
}
sort(b + 1, b + q + 1);
reverse(b + 1, b + q + 1);
for(int i = 1; i <= q; i++){
while(k >= 1 and a[k].st >= b[i].st.st){
// cout << a[k].nd.st << " " << a[k].nd.nd << " geldi" << endl << endl;
up1(1, 1, n, a[k].nd.st, a[k].nd.nd);
k--;
}
// cout << b[i].st.nd << " icin bul " << n << " " << m << endl;
ans[b[i].st.nd] = qu1(1, 1, n, min(n, b[i].nd.st), min(m, b[i].nd.nd) );
}
for(int i = 1; i <= q; i++)
printf("%d\n", ans[i]);
return 0;
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&k ,&q);
~~~~~^~~~~~~~~~~~~~~~
examination.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a[i].nd.st ,&a[i].nd.nd);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d" ,&b[i].nd.st ,&b[i].nd.nd,&b[i].st.st);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Runtime error |
52 ms |
25072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
30832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
135 ms |
30832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Runtime error |
52 ms |
25072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
