oj.uz

Submission #1041997

# Submission time Handle Problem Language Result Execution time Memory
1041997 2024-08-02T11:52:39 Z 1L1YA Examination (JOI19_examination) C++17
100 / 100
 629 ms 91568 KB 
//1L1YA

#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=2e5+11;
const int lg=23;

int n,m,q,a[N],b[N],x[N],y[N],z[N],ans[N];
vector<pii> Q,vec;
vector<int> comp;
struct node{
	vector<int> vc,fen;
}seg[N<<2];

void upd(int id,int x,int y){
	int sz=SZ(seg[id].vc);
	for(x=sz-x;x<=sz;x+=x&-x)	seg[id].fen[x]+=y;
}

int gett(int id,int x){
	int sz=SZ(seg[id].vc),ans=0;
	for(x=sz-x;x;x-=x&-x)	ans+=seg[id].fen[x];
	return ans;
}

void build1(int pos,int val,int id=1,int l=0,int r=m){
	seg[id].vc.Pb(val);
	if(r-l==1)	return;
	if(pos<mid)	build1(pos,val,lc,l,mid);
	else	build1(pos,val,rc,mid,r);
}

void build2(int ql,int qr,int val,int id=1,int l=0,int r=m){
	if(qr<=l || ql>=r)	return;
	if(ql<=l && r<=qr){
		seg[id].vc.Pb(val);
		return;
	}
	build2(ql,qr,val,lc,l,mid);
	build2(ql,qr,val,rc,mid,r);
}

void build(int id=1,int l=0,int r=m){
	sort(all(seg[id].vc));
	seg[id].vc.resize(unique(all(seg[id].vc))-seg[id].vc.begin());
	seg[id].fen.resize(SZ(seg[id].vc)+1);
	if(r-l==1)	return;
	build(lc,l,mid);
	build(rc,mid,r);
}

void modify(int pos,int val,int id=1,int l=0,int r=m){
	upd(id,lower_bound(all(seg[id].vc),val)-seg[id].vc.begin(),1);
	if(r-l==1)	return;
	if(pos<mid)	modify(pos,val,lc,l,mid);
	else	modify(pos,val,rc,mid,r);
}

int get(int ql,int qr,int val,int id=1,int l=0,int r=m){
	if(qr<=l || ql>=r)	return 0;
	if(ql<=l && r<=qr)	return gett(id,lower_bound(all(seg[id].vc),val)-seg[id].vc.begin());
	return get(ql,qr,val,lc,l,mid)+get(ql,qr,val,rc,mid,r);
}

int main(){
	FastIO

	cin >> n >> q;
	for(int i=1;i<=n;i++){
		cin >> a[i] >> b[i];
		comp.Pb(b[i]);
		vec.Pb({a[i],i});
	}
	for(int i=1;i<=q;i++){
		cin >> x[i] >> y[i] >> z[i];
		comp.Pb(y[i]);
		Q.Pb({x[i],i});
	}
	sort(all(Q));
	sort(all(vec),greater<>());
	sort(all(comp));
	comp.resize(unique(all(comp))-comp.begin());
	m=SZ(comp);
	for(int i=1;i<=n;i++)	b[i]=lower_bound(all(comp),b[i])-comp.begin(),build1(b[i],a[i]+comp[b[i]]);
	for(int i=1;i<=q;i++)	y[i]=lower_bound(all(comp),y[i])-comp.begin(),build2(y[i],m,z[i]);
	build();
	for(auto [x,i]: vec){
		while(SZ(Q) && Q.back().F>x){
			int j=Q.back().S;Q.pop_back();
			ans[j]=get(y[j],m,z[j]);
		}
		modify(b[i],a[i]+comp[b[i]]);
	}
	while(SZ(Q)){
		int j=Q.back().S;Q.pop_back();
		ans[j]=get(y[j],m,z[j]);
	}
	for(int i=1;i<=q;i++)	cout << ans[i] << endl;

	return 0;
}

Compilation message

examination.cpp: In function 'void build1(int, int, int, int, int)':
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:58:9: note: in expansion of macro 'mid'
   58 |  if(pos<mid) build1(pos,val,lc,l,mid);
      |         ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:58:34: note: in expansion of macro 'mid'
   58 |  if(pos<mid) build1(pos,val,lc,l,mid);
      |                                  ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:59:25: note: in expansion of macro 'mid'
   59 |  else build1(pos,val,rc,mid,r);
      |                         ^~~
examination.cpp: In function 'void build2(int, int, int, int, int, int)':
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:68:24: note: in expansion of macro 'mid'
   68 |  build2(ql,qr,val,lc,l,mid);
      |                        ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:69:22: note: in expansion of macro 'mid'
   69 |  build2(ql,qr,val,rc,mid,r);
      |                      ^~~
examination.cpp: In function 'void build(int, int, int)':
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:77:13: note: in expansion of macro 'mid'
   77 |  build(lc,l,mid);
      |             ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:78:11: note: in expansion of macro 'mid'
   78 |  build(rc,mid,r);
      |           ^~~
examination.cpp: In function 'void modify(int, int, int, int, int)':
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:84:9: note: in expansion of macro 'mid'
   84 |  if(pos<mid) modify(pos,val,lc,l,mid);
      |         ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:84:34: note: in expansion of macro 'mid'
   84 |  if(pos<mid) modify(pos,val,lc,l,mid);
      |                                  ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:85:25: note: in expansion of macro 'mid'
   85 |  else modify(pos,val,rc,mid,r);
      |                         ^~~
examination.cpp: In function 'int get(int, int, int, int, int, int)':
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:91:28: note: in expansion of macro 'mid'
   91 |  return get(ql,qr,val,lc,l,mid)+get(ql,qr,val,rc,mid,r);
      |                            ^~~
examination.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
examination.cpp:91:50: note: in expansion of macro 'mid'
   91 |  return get(ql,qr,val,lc,l,mid)+get(ql,qr,val,rc,mid,r);
      |                                                  ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41564 KB Output is correct
2 Correct 6 ms 41564 KB Output is correct
3 Correct 5 ms 41564 KB Output is correct
4 Correct 7 ms 41820 KB Output is correct
5 Correct 6 ms 41672 KB Output is correct
6 Correct 5 ms 41560 KB Output is correct
7 Correct 15 ms 42844 KB Output is correct
8 Correct 15 ms 42844 KB Output is correct
9 Correct 15 ms 42840 KB Output is correct
10 Correct 8 ms 42076 KB Output is correct
11 Correct 14 ms 42948 KB Output is correct
12 Correct 7 ms 41880 KB Output is correct
13 Correct 14 ms 42932 KB Output is correct
14 Correct 15 ms 42844 KB Output is correct
15 Correct 13 ms 42844 KB Output is correct
16 Correct 13 ms 40792 KB Output is correct
17 Correct 9 ms 42076 KB Output is correct
18 Correct 7 ms 41872 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 73788 KB Output is correct
2 Correct 408 ms 73728 KB Output is correct
3 Correct 392 ms 73528 KB Output is correct
4 Correct 108 ms 51180 KB Output is correct
5 Correct 409 ms 71136 KB Output is correct
6 Correct 68 ms 49208 KB Output is correct
7 Correct 388 ms 73576 KB Output is correct
8 Correct 383 ms 71996 KB Output is correct
9 Correct 347 ms 71984 KB Output is correct
10 Correct 390 ms 70716 KB Output is correct
11 Correct 70 ms 48424 KB Output is correct
12 Correct 45 ms 47596 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 73788 KB Output is correct
2 Correct 408 ms 73728 KB Output is correct
3 Correct 392 ms 73528 KB Output is correct
4 Correct 108 ms 51180 KB Output is correct
5 Correct 409 ms 71136 KB Output is correct
6 Correct 68 ms 49208 KB Output is correct
7 Correct 388 ms 73576 KB Output is correct
8 Correct 383 ms 71996 KB Output is correct
9 Correct 347 ms 71984 KB Output is correct
10 Correct 390 ms 70716 KB Output is correct
11 Correct 70 ms 48424 KB Output is correct
12 Correct 45 ms 47596 KB Output is correct
13 Correct 527 ms 76860 KB Output is correct
14 Correct 501 ms 76604 KB Output is correct
15 Correct 425 ms 73784 KB Output is correct
16 Correct 135 ms 52028 KB Output is correct
17 Correct 505 ms 74036 KB Output is correct
18 Correct 73 ms 49216 KB Output is correct
19 Correct 515 ms 76604 KB Output is correct
20 Correct 520 ms 76844 KB Output is correct
21 Correct 501 ms 76092 KB Output is correct
22 Correct 395 ms 70716 KB Output is correct
23 Correct 68 ms 48440 KB Output is correct
24 Correct 44 ms 47676 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41564 KB Output is correct
2 Correct 6 ms 41564 KB Output is correct
3 Correct 5 ms 41564 KB Output is correct
4 Correct 7 ms 41820 KB Output is correct
5 Correct 6 ms 41672 KB Output is correct
6 Correct 5 ms 41560 KB Output is correct
7 Correct 15 ms 42844 KB Output is correct
8 Correct 15 ms 42844 KB Output is correct
9 Correct 15 ms 42840 KB Output is correct
10 Correct 8 ms 42076 KB Output is correct
11 Correct 14 ms 42948 KB Output is correct
12 Correct 7 ms 41880 KB Output is correct
13 Correct 14 ms 42932 KB Output is correct
14 Correct 15 ms 42844 KB Output is correct
15 Correct 13 ms 42844 KB Output is correct
16 Correct 13 ms 40792 KB Output is correct
17 Correct 9 ms 42076 KB Output is correct
18 Correct 7 ms 41872 KB Output is correct
19 Correct 395 ms 73788 KB Output is correct
20 Correct 408 ms 73728 KB Output is correct
21 Correct 392 ms 73528 KB Output is correct
22 Correct 108 ms 51180 KB Output is correct
23 Correct 409 ms 71136 KB Output is correct
24 Correct 68 ms 49208 KB Output is correct
25 Correct 388 ms 73576 KB Output is correct
26 Correct 383 ms 71996 KB Output is correct
27 Correct 347 ms 71984 KB Output is correct
28 Correct 390 ms 70716 KB Output is correct
29 Correct 70 ms 48424 KB Output is correct
30 Correct 45 ms 47596 KB Output is correct
31 Correct 527 ms 76860 KB Output is correct
32 Correct 501 ms 76604 KB Output is correct
33 Correct 425 ms 73784 KB Output is correct
34 Correct 135 ms 52028 KB Output is correct
35 Correct 505 ms 74036 KB Output is correct
36 Correct 73 ms 49216 KB Output is correct
37 Correct 515 ms 76604 KB Output is correct
38 Correct 520 ms 76844 KB Output is correct
39 Correct 501 ms 76092 KB Output is correct
40 Correct 395 ms 70716 KB Output is correct
41 Correct 68 ms 48440 KB Output is correct
42 Correct 44 ms 47676 KB Output is correct
43 Correct 608 ms 91332 KB Output is correct
44 Correct 604 ms 91496 KB Output is correct
45 Correct 612 ms 91188 KB Output is correct
46 Correct 133 ms 53704 KB Output is correct
47 Correct 629 ms 89652 KB Output is correct
48 Correct 74 ms 49000 KB Output is correct
49 Correct 599 ms 91308 KB Output is correct
50 Correct 609 ms 91568 KB Output is correct
51 Correct 590 ms 91432 KB Output is correct
52 Correct 595 ms 89640 KB Output is correct
53 Correct 75 ms 49720 KB Output is correct