#include<bits/stdc++.h>
//#define int long long
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define all(a) a.begin(),a.end()
#define pi 3.14159265359
#define TASKNAME "examination"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef pair<ii,ii> iv;
const int MAXN = 100005;
const int block = 316;
const int MAXBLOCK = MAXN / block;
int n,q,x,start,b;
iv score[MAXN], original[MAXN];
int nxt[6*MAXN],prep[MAXN],rev[MAXN],answer[MAXN];
struct BIT{
vector<int> roirachoa;
vector<int> T;
int sz=0;
void init(int _sz){
sz = _sz;
T.resize(_sz+3,0);
}
void upd(int id,int x){
for(int i=id;i>0;i-=i&(-i)){
T[i] += x;
}
}
int get(int id){
int res = 0;
for(int i=id;i<=sz;i+=i&(-i)){
res += T[i];
}
return res;
}
int getval(int x){
return lower_bound(all(roirachoa),x) - roirachoa.begin() + 1;
}
};
BIT st[MAXBLOCK*4];
void push(int node,int l,int r,int pos,int x){
// cout<<node<<' '<<l<<' '<<r<<' '<<pos<<' '<<x<<endl;
st[node].roirachoa.pb(x);
if (l==r) return;
int mid = (l+r)>>1;
if (pos<=mid) push(node<<1,l,mid,pos,x);
else push(node<<1|1,mid+1,r,pos,x);
}
vector<int> listval;
vector<iv> query;
void update(int node,int l,int r,int pos,int x){
st[node].upd(st[node].getval(x),1);
// cout<<"UPD: "<<node<<' '<<l<<' '<<r<<' '<<x<<' '<<st[node].getval(x)<<endl;
if (l==r) return;
int mid = (l+r)>>1;
if (pos <= mid){
update(node<<1,l,mid,pos,x);
}
else update(node<<1|1,mid+1,r,pos,x);
}
int getrange(int node,int l,int r,int u,int v,int x){
if (l>=u and r<=v){
// cout<<"GET: "<<node<<' '<<l<<' '<<r<<' '<<x<<' '<<st[node].getval(x)<<endl;
return st[node].get(st[node].getval(x));
}
if (l>v or r<u) return 0;
int mid = (l+r)>>1;
return getrange(node<<1,l,mid,u,v,x) + getrange(node<<1|1,mid+1,r,u,v,x);
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>score[i].se.fi>>score[i].se.se;
score[i].fi.se = score[i].se.fi + score[i].se.se;
listval.pb(score[i].se.fi);
listval.pb(score[i].se.se);
listval.pb(score[i].fi.se);
}
sort(score+1,score+1+n,[](const iv &a,const iv &b){
return a.se.fi < b.se.fi;
});
for(int i=1;i<=q;i++){
int x,y,z;
cin>>x>>y>>z;
listval.pb(x);
listval.pb(y);
listval.pb(z);
query.pb({{i,x},{y,z}});
}
sort(listval.begin(),listval.end());
listval.erase(unique(listval.begin(),listval.end()),listval.end());
for(int i=1;i<=max(q,n);i++){
if (i<=n){
score[i].se.fi = lower_bound(all(listval),score[i].se.fi) - listval.begin() + 1;
score[i].se.se = lower_bound(all(listval),score[i].se.se) - listval.begin() + 1;
score[i].fi.se = lower_bound(all(listval),score[i].fi.se) - listval.begin() + 1;
}
if (i<=q){
query[i-1].se.fi = lower_bound(all(listval),query[i-1].se.fi) - listval.begin() + 1;
query[i-1].se.se = lower_bound(all(listval),query[i-1].se.se) - listval.begin() + 1;
query[i-1].fi.se = lower_bound(all(listval),query[i-1].fi.se) - listval.begin() + 1;
}
}
for(int i=1;i<=n;i++){
score[i].fi.fi = i;
original[i] = score[i];
}
int ptr = 1;
for(int i=1;i<=listval.size();i++){
while(ptr <= n and original[ptr].se.fi < i){
ptr++;
}
if (ptr<=n) nxt[i] = original[ptr].fi.fi;
else nxt[i] = n+1;
}
sort(query.begin(),query.end(),[](const iv &a,const iv &b){
return a.se.se > b.se.se;
});
sort(score+1,score+1+n,[](const iv &a,const iv &b){
return a.fi.se > b.fi.se;
});
// for(int i=1;i<=n;i++){
// cout<<score[i].fi.se<<' '<<score[i].se.fi<<' '<<score[i].se.se<<endl;
// }
for(int i=1;i<=n;i++){
prep[i] = i / block;
push(1,0,MAXBLOCK,prep[i],original[i].se.se);
}
for(int i=1;i<MAXBLOCK*4;i++){
sort(all(st[i].roirachoa));
// cout<<"NODE: "<<i<<endl;
// for(auto x: st[i].roirachoa){
// cout<<x<<' ';
// }
// cout<<endl;
st[i].roirachoa.erase(unique(all(st[i].roirachoa)),st[i].roirachoa.end());
st[i].init(sz(st[i].roirachoa));
}
ptr = 1;
for(int i=0;i<query.size();i++){
while(ptr <= n and score[ptr].fi.se >= query[i].se.se){
int RealIndex = score[ptr].fi.fi;
rev[RealIndex]++;
int b = prep[RealIndex];
// cout<<b<<' '<<score[ptr].se.se<<endl;
update(1,0,MAXBLOCK,b,score[ptr].se.se);
ptr++;
}
start = nxt[query[i].fi.se];
b = prep[start];
// cout<<"START: "<<start<<' '<<b<<endl;
if (start > n) continue;
for(int j=start;j<=n;j++){
if (original[j].se.fi >= query[i].fi.se and
original[j].se.se >= query[i].se.fi and
original[j].fi.se >= query[i].se.se and
rev[j] > 0){
answer[query[i].fi.fi]++;
}
if (prep[j] != prep[j+1]) {
break;
}
}
if (b+1 <= MAXBLOCK) answer[query[i].fi.fi] += getrange(1,0,MAXBLOCK,b+1,MAXBLOCK,query[i].se.fi);
}
for(int i=1;i<=q;i++){
cout<<answer[i]<<endl;
}
}
Compilation message
examination.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
4 | #pragma GCC optimization ("O3")
|
examination.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
5 | #pragma GCC optimization ("unroll-loops")
|
examination.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
87 | main()
| ^~~~
examination.cpp: In function 'int main()':
examination.cpp:133:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(int i=1;i<=listval.size();i++){
| ~^~~~~~~~~~~~~~~~
examination.cpp:166:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for(int i=0;i<query.size();i++){
| ~^~~~~~~~~~~~~
examination.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6488 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 ms |
6492 KB |
Output is correct |
7 |
Correct |
11 ms |
7036 KB |
Output is correct |
8 |
Correct |
11 ms |
7260 KB |
Output is correct |
9 |
Correct |
11 ms |
7260 KB |
Output is correct |
10 |
Correct |
8 ms |
7004 KB |
Output is correct |
11 |
Correct |
10 ms |
7200 KB |
Output is correct |
12 |
Correct |
6 ms |
6948 KB |
Output is correct |
13 |
Correct |
11 ms |
7260 KB |
Output is correct |
14 |
Correct |
10 ms |
7260 KB |
Output is correct |
15 |
Correct |
10 ms |
7260 KB |
Output is correct |
16 |
Correct |
8 ms |
7000 KB |
Output is correct |
17 |
Correct |
6 ms |
7000 KB |
Output is correct |
18 |
Correct |
3 ms |
7000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
427 ms |
20868 KB |
Output is correct |
2 |
Correct |
414 ms |
19656 KB |
Output is correct |
3 |
Correct |
417 ms |
20984 KB |
Output is correct |
4 |
Correct |
219 ms |
16444 KB |
Output is correct |
5 |
Correct |
345 ms |
21000 KB |
Output is correct |
6 |
Correct |
179 ms |
17440 KB |
Output is correct |
7 |
Correct |
440 ms |
20568 KB |
Output is correct |
8 |
Correct |
379 ms |
20024 KB |
Output is correct |
9 |
Correct |
375 ms |
19548 KB |
Output is correct |
10 |
Correct |
291 ms |
19400 KB |
Output is correct |
11 |
Correct |
152 ms |
19264 KB |
Output is correct |
12 |
Correct |
81 ms |
17688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
427 ms |
20868 KB |
Output is correct |
2 |
Correct |
414 ms |
19656 KB |
Output is correct |
3 |
Correct |
417 ms |
20984 KB |
Output is correct |
4 |
Correct |
219 ms |
16444 KB |
Output is correct |
5 |
Correct |
345 ms |
21000 KB |
Output is correct |
6 |
Correct |
179 ms |
17440 KB |
Output is correct |
7 |
Correct |
440 ms |
20568 KB |
Output is correct |
8 |
Correct |
379 ms |
20024 KB |
Output is correct |
9 |
Correct |
375 ms |
19548 KB |
Output is correct |
10 |
Correct |
291 ms |
19400 KB |
Output is correct |
11 |
Correct |
152 ms |
19264 KB |
Output is correct |
12 |
Correct |
81 ms |
17688 KB |
Output is correct |
13 |
Correct |
457 ms |
24316 KB |
Output is correct |
14 |
Correct |
473 ms |
23700 KB |
Output is correct |
15 |
Correct |
421 ms |
22552 KB |
Output is correct |
16 |
Correct |
248 ms |
19328 KB |
Output is correct |
17 |
Correct |
377 ms |
22048 KB |
Output is correct |
18 |
Correct |
180 ms |
17796 KB |
Output is correct |
19 |
Correct |
460 ms |
22592 KB |
Output is correct |
20 |
Correct |
458 ms |
23868 KB |
Output is correct |
21 |
Correct |
453 ms |
23476 KB |
Output is correct |
22 |
Correct |
298 ms |
22332 KB |
Output is correct |
23 |
Correct |
178 ms |
18944 KB |
Output is correct |
24 |
Correct |
83 ms |
17932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6488 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 ms |
6492 KB |
Output is correct |
7 |
Correct |
11 ms |
7036 KB |
Output is correct |
8 |
Correct |
11 ms |
7260 KB |
Output is correct |
9 |
Correct |
11 ms |
7260 KB |
Output is correct |
10 |
Correct |
8 ms |
7004 KB |
Output is correct |
11 |
Correct |
10 ms |
7200 KB |
Output is correct |
12 |
Correct |
6 ms |
6948 KB |
Output is correct |
13 |
Correct |
11 ms |
7260 KB |
Output is correct |
14 |
Correct |
10 ms |
7260 KB |
Output is correct |
15 |
Correct |
10 ms |
7260 KB |
Output is correct |
16 |
Correct |
8 ms |
7000 KB |
Output is correct |
17 |
Correct |
6 ms |
7000 KB |
Output is correct |
18 |
Correct |
3 ms |
7000 KB |
Output is correct |
19 |
Correct |
427 ms |
20868 KB |
Output is correct |
20 |
Correct |
414 ms |
19656 KB |
Output is correct |
21 |
Correct |
417 ms |
20984 KB |
Output is correct |
22 |
Correct |
219 ms |
16444 KB |
Output is correct |
23 |
Correct |
345 ms |
21000 KB |
Output is correct |
24 |
Correct |
179 ms |
17440 KB |
Output is correct |
25 |
Correct |
440 ms |
20568 KB |
Output is correct |
26 |
Correct |
379 ms |
20024 KB |
Output is correct |
27 |
Correct |
375 ms |
19548 KB |
Output is correct |
28 |
Correct |
291 ms |
19400 KB |
Output is correct |
29 |
Correct |
152 ms |
19264 KB |
Output is correct |
30 |
Correct |
81 ms |
17688 KB |
Output is correct |
31 |
Correct |
457 ms |
24316 KB |
Output is correct |
32 |
Correct |
473 ms |
23700 KB |
Output is correct |
33 |
Correct |
421 ms |
22552 KB |
Output is correct |
34 |
Correct |
248 ms |
19328 KB |
Output is correct |
35 |
Correct |
377 ms |
22048 KB |
Output is correct |
36 |
Correct |
180 ms |
17796 KB |
Output is correct |
37 |
Correct |
460 ms |
22592 KB |
Output is correct |
38 |
Correct |
458 ms |
23868 KB |
Output is correct |
39 |
Correct |
453 ms |
23476 KB |
Output is correct |
40 |
Correct |
298 ms |
22332 KB |
Output is correct |
41 |
Correct |
178 ms |
18944 KB |
Output is correct |
42 |
Correct |
83 ms |
17932 KB |
Output is correct |
43 |
Correct |
486 ms |
25452 KB |
Output is correct |
44 |
Correct |
499 ms |
26564 KB |
Output is correct |
45 |
Correct |
490 ms |
26692 KB |
Output is correct |
46 |
Correct |
261 ms |
21316 KB |
Output is correct |
47 |
Correct |
425 ms |
23360 KB |
Output is correct |
48 |
Correct |
179 ms |
18784 KB |
Output is correct |
49 |
Correct |
486 ms |
24788 KB |
Output is correct |
50 |
Correct |
444 ms |
25180 KB |
Output is correct |
51 |
Correct |
456 ms |
25656 KB |
Output is correct |
52 |
Correct |
349 ms |
23100 KB |
Output is correct |
53 |
Correct |
167 ms |
20140 KB |
Output is correct |