oj.uz

Submission #613212

# Submission time Handle Problem Language Result Execution time Memory
613212 2022-07-30T04:01:08 Z temporary_juggernaut Examination (JOI19_examination) C++14
100 / 100
 1697 ms 206328 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
vector<array<int,4>>vec;
int ans[100005];
const int N=2e5;
struct SegmentTree{
	struct node{
		int lson,rson,sum;
		node(){
			lson=rson=sum=0;
		}
	};
	vector<node>tree={node(),node()};
	int timer=2;
	void update(int pos,int v=1,int l=1,int r=N){
		tree[v].sum++;
		if(l==r)return;
		int mid=(l+r)>>1;
		if(pos<=mid){
			if(!tree[v].lson){
				tree.push_back(node());
				tree[v].lson=timer++;
			}
			update(pos,tree[v].lson,l,mid);
		}else{
			if(!tree[v].rson){
				tree.push_back(node());
				tree[v].rson=timer++;
			}
			update(pos,tree[v].rson,mid+1,r);
		}
	}
	int get(int ql,int qr,int v=1,int l=1,int r=N){
		if(r<ql||qr<l||!v)return 0;
		if(ql<=l&&r<=qr)return tree[v].sum;
		int mid=(l+r)>>1;
		return get(ql,qr,tree[v].lson,l,mid)+get(ql,qr,tree[v].rson,mid+1,r);
	}
}fen[200005];
void add(int x,int y){
	x=N-x+1;
	for(;x<=N;x+=(x&-x))fen[x].update(y);
}
int sum(int x,int y){
	int ans=0;
	for(;x;x-=(x&-x))ans+=fen[x].get(y,N);
	return ans;
}
int gt(int x,int y){
	return sum(N-x+1,y);
}
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	vector<int>X,Y;
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		X.push_back(x);
		Y.push_back(y);
		vec.push_back({-x-y,0,x,y});
	}
	for(int i=1;i<=q;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		X.push_back(x);
		Y.push_back(y);
		vec.push_back({-z,i,x,y});
	}
	sort(vec.begin(),vec.end());
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());
	sort(Y.begin(),Y.end());
	Y.erase(unique(Y.begin(),Y.end()),Y.end());
	map<int,int>idx,idy;
	int timer=1;
	for(int to:X)idx[to]=timer++;
	timer=1;
	for(int to:Y)idy[to]=timer++;
	for(auto query:vec){
		query[2]=idx[query[2]];
		query[3]=idy[query[3]];
		if(!query[1])add(query[2],query[3]);
		else ans[query[1]]=gt(query[2],query[3]);
	}
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
examination.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~
examination.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d%d%d",&x,&y,&z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12756 KB Output is correct
2 Correct 13 ms 12788 KB Output is correct
3 Correct 13 ms 12768 KB Output is correct
4 Correct 12 ms 12800 KB Output is correct
5 Correct 12 ms 12832 KB Output is correct
6 Correct 15 ms 12716 KB Output is correct
7 Correct 25 ms 16836 KB Output is correct
8 Correct 29 ms 16804 KB Output is correct
9 Correct 31 ms 16808 KB Output is correct
10 Correct 22 ms 14888 KB Output is correct
11 Correct 18 ms 13908 KB Output is correct
12 Correct 17 ms 13020 KB Output is correct
13 Correct 30 ms 16852 KB Output is correct
14 Correct 32 ms 16892 KB Output is correct
15 Correct 34 ms 16936 KB Output is correct
16 Correct 20 ms 13520 KB Output is correct
17 Correct 26 ms 14804 KB Output is correct
18 Correct 15 ms 13012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1289 ms 158664 KB Output is correct
2 Correct 1261 ms 158560 KB Output is correct
3 Correct 1257 ms 158840 KB Output is correct
4 Correct 426 ms 53232 KB Output is correct
5 Correct 362 ms 35228 KB Output is correct
6 Correct 155 ms 19800 KB Output is correct
7 Correct 1128 ms 153488 KB Output is correct
8 Correct 1087 ms 153728 KB Output is correct
9 Correct 1094 ms 148528 KB Output is correct
10 Correct 235 ms 27172 KB Output is correct
11 Correct 350 ms 50168 KB Output is correct
12 Correct 171 ms 19476 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1289 ms 158664 KB Output is correct
2 Correct 1261 ms 158560 KB Output is correct
3 Correct 1257 ms 158840 KB Output is correct
4 Correct 426 ms 53232 KB Output is correct
5 Correct 362 ms 35228 KB Output is correct
6 Correct 155 ms 19800 KB Output is correct
7 Correct 1128 ms 153488 KB Output is correct
8 Correct 1087 ms 153728 KB Output is correct
9 Correct 1094 ms 148528 KB Output is correct
10 Correct 235 ms 27172 KB Output is correct
11 Correct 350 ms 50168 KB Output is correct
12 Correct 171 ms 19476 KB Output is correct
13 Correct 1597 ms 158832 KB Output is correct
14 Correct 1550 ms 158324 KB Output is correct
15 Correct 1697 ms 158896 KB Output is correct
16 Correct 493 ms 53252 KB Output is correct
17 Correct 408 ms 35404 KB Output is correct
18 Correct 224 ms 19776 KB Output is correct
19 Correct 1253 ms 158344 KB Output is correct
20 Correct 1557 ms 159040 KB Output is correct
21 Correct 1187 ms 155012 KB Output is correct
22 Correct 251 ms 27104 KB Output is correct
23 Correct 425 ms 50184 KB Output is correct
24 Correct 167 ms 19460 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12756 KB Output is correct
2 Correct 13 ms 12788 KB Output is correct
3 Correct 13 ms 12768 KB Output is correct
4 Correct 12 ms 12800 KB Output is correct
5 Correct 12 ms 12832 KB Output is correct
6 Correct 15 ms 12716 KB Output is correct
7 Correct 25 ms 16836 KB Output is correct
8 Correct 29 ms 16804 KB Output is correct
9 Correct 31 ms 16808 KB Output is correct
10 Correct 22 ms 14888 KB Output is correct
11 Correct 18 ms 13908 KB Output is correct
12 Correct 17 ms 13020 KB Output is correct
13 Correct 30 ms 16852 KB Output is correct
14 Correct 32 ms 16892 KB Output is correct
15 Correct 34 ms 16936 KB Output is correct
16 Correct 20 ms 13520 KB Output is correct
17 Correct 26 ms 14804 KB Output is correct
18 Correct 15 ms 13012 KB Output is correct
19 Correct 1289 ms 158664 KB Output is correct
20 Correct 1261 ms 158560 KB Output is correct
21 Correct 1257 ms 158840 KB Output is correct
22 Correct 426 ms 53232 KB Output is correct
23 Correct 362 ms 35228 KB Output is correct
24 Correct 155 ms 19800 KB Output is correct
25 Correct 1128 ms 153488 KB Output is correct
26 Correct 1087 ms 153728 KB Output is correct
27 Correct 1094 ms 148528 KB Output is correct
28 Correct 235 ms 27172 KB Output is correct
29 Correct 350 ms 50168 KB Output is correct
30 Correct 171 ms 19476 KB Output is correct
31 Correct 1597 ms 158832 KB Output is correct
32 Correct 1550 ms 158324 KB Output is correct
33 Correct 1697 ms 158896 KB Output is correct
34 Correct 493 ms 53252 KB Output is correct
35 Correct 408 ms 35404 KB Output is correct
36 Correct 224 ms 19776 KB Output is correct
37 Correct 1253 ms 158344 KB Output is correct
38 Correct 1557 ms 159040 KB Output is correct
39 Correct 1187 ms 155012 KB Output is correct
40 Correct 251 ms 27104 KB Output is correct
41 Correct 425 ms 50184 KB Output is correct
42 Correct 167 ms 19460 KB Output is correct
43 Correct 1465 ms 206328 KB Output is correct
44 Correct 1384 ms 206048 KB Output is correct
45 Correct 1575 ms 205880 KB Output is correct
46 Correct 597 ms 83632 KB Output is correct
47 Correct 339 ms 47176 KB Output is correct
48 Correct 137 ms 19600 KB Output is correct
49 Correct 1296 ms 194820 KB Output is correct
50 Correct 1365 ms 199176 KB Output is correct
51 Correct 1205 ms 186484 KB Output is correct
52 Correct 271 ms 36468 KB Output is correct
53 Correct 478 ms 80576 KB Output is correct