oj.uz

Submission #152443

# Submission time Handle Problem Language Result Execution time Memory
152443 2019-09-08T03:11:10 Z cheetose Examination (JOI19_examination) C++11
43 / 100
 3000 ms 1029048 KB 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

struct xnode{
	int yroot,L,R;
	xnode(){
		yroot=-1,L=-1,R=-1;
	}
};
struct ynode{
	int val,L,R;
	ynode(){
		val=0;
		L=-1,R=-1;
	}
};
vector<xnode> xtree;
vector<ynode> ytree;
int xinit(){
	xnode x;
	xtree.pb(x);
	return xtree.size()-1;
}
int yinit(){
	ynode y;
	ytree.pb(y);
	return ytree.size()-1;
}
void yupd(int node,int S,int E,int y)
{
	ytree[node].val++;
	if(S==E)return;
	int M=(S+E)>>1;
	if(y<=M)
	{
		if(ytree[node].L==-1)
		{
			int next=yinit();
			ytree[node].L=next;
		}
		yupd(ytree[node].L,S,M,y);
	}
	else
	{
		if(ytree[node].R==-1)
		{
			int next=yinit();
			ytree[node].R=next;
		}
		yupd(ytree[node].R,M+1,E,y);
	}
}
void upd(int node,int S,int E,int x,int y)//(x,y)좌표값 1증가
{
	if(xtree[node].yroot==-1)
	{
		int next=yinit();
		xtree[node].yroot=next;
	}
	yupd(xtree[node].yroot,0,(int)1e9,y);
	if(S==E)return;
	int M=(S+E)>>1;
	if(x<=M)
	{
		if(xtree[node].L==-1)
		{
			int next=xinit();
			xtree[node].L=next;
		}
		upd(xtree[node].L,S,M,x,y);
	}
	else
	{
		if(xtree[node].R==-1)
		{
			int next=xinit();
			xtree[node].R=next;
		}
		upd(xtree[node].R,M+1,E,x,y);
	}
}
int yfind(int node,int S,int E,int y1,int y2)
{
	if(y1>E || y2<S)return 0;
	if(y1<=S && y2>=E)return ytree[node].val;
	int res=0;
	if(~ytree[node].L)res+=yfind(ytree[node].L,S,(S+E)/2,y1,y2);
	if(~ytree[node].R)res+=yfind(ytree[node].R,(S+E)/2+1,E,y1,y2);
	return res;
}
int find(int node,int S,int E,int x1,int x2,int y1,int y2)
{
	if(x1>E || x2<S)return 0;
	if(x1<=S && x2>=E)
	{
		if(xtree[node].yroot==-1)return 0;
		return yfind(xtree[node].yroot,0,(int)1e9,y1,y2);
	}
	int res=0;
	if(~xtree[node].L)res+=find(xtree[node].L,S,(S+E)/2,x1,x2,y1,y2);
	if(~xtree[node].R)res+=find(xtree[node].R,(S+E)/2+1,E,x1,x2,y1,y2);
	return res;
}

struct query{
	int x,y,z,i;
	bool operator <(const query &O)const{
		return z>O.z;
	}
}q[100000];
Pi p[100000];
int ans[100000];
int main() {
	xinit();
	int n,Q;
	scanf("%d%d",&n,&Q);
	fup(i,0,n-1,1)
		scanf("%d%d",&p[i].X,&p[i].Y);
	sort(p,p+n,[&](Pi p1,Pi p2){return p1.X+p1.Y>p2.X+p2.Y;});
	fup(i,0,Q-1,1)
	{
		scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
		q[i].i=i;
	}
	sort(q,q+Q);
	for(int i=0,j=0;i<Q;i++)
	{
		while(j<n && p[j].X+p[j].Y>=q[i].z)
		{
			upd(0,0,(int)1e9,p[j].X,p[j].Y);
			j++;
		}
		ans[q[i].i]=find(0,0,(int)1e9,q[i].x,(int)1e9,q[i].y,(int)1e9);
	}
	fup(i,0,Q-1,1)printf("%d\n",ans[i]);
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:175:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&Q);
  ~~~~~^~~~~~~~~~~~~~
examination.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p[i].X,&p[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:181:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 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 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 121 ms 50968 KB Output is correct
8 Correct 107 ms 51020 KB Output is correct
9 Correct 122 ms 50968 KB Output is correct
10 Correct 79 ms 26224 KB Output is correct
11 Correct 69 ms 25156 KB Output is correct
12 Correct 20 ms 504 KB Output is correct
13 Correct 107 ms 51040 KB Output is correct
14 Correct 106 ms 50996 KB Output is correct
15 Correct 107 ms 50996 KB Output is correct
16 Correct 67 ms 25160 KB Output is correct
17 Correct 68 ms 26196 KB Output is correct
18 Correct 18 ms 504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2673 ms 401476 KB Output is correct
2 Correct 2782 ms 401560 KB Output is correct
3 Correct 2706 ms 401532 KB Output is correct
4 Correct 1097 ms 104224 KB Output is correct
5 Correct 954 ms 101332 KB Output is correct
6 Correct 591 ms 3936 KB Output is correct
7 Correct 2623 ms 401344 KB Output is correct
8 Correct 2596 ms 401616 KB Output is correct
9 Correct 2479 ms 401484 KB Output is correct
10 Correct 783 ms 101408 KB Output is correct
11 Correct 894 ms 106384 KB Output is correct
12 Correct 528 ms 3276 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2673 ms 401476 KB Output is correct
2 Correct 2782 ms 401560 KB Output is correct
3 Correct 2706 ms 401532 KB Output is correct
4 Correct 1097 ms 104224 KB Output is correct
5 Correct 954 ms 101332 KB Output is correct
6 Correct 591 ms 3936 KB Output is correct
7 Correct 2623 ms 401344 KB Output is correct
8 Correct 2596 ms 401616 KB Output is correct
9 Correct 2479 ms 401484 KB Output is correct
10 Correct 783 ms 101408 KB Output is correct
11 Correct 894 ms 106384 KB Output is correct
12 Correct 528 ms 3276 KB Output is correct
13 Correct 2545 ms 403628 KB Output is correct
14 Correct 2708 ms 402032 KB Output is correct
15 Correct 2722 ms 402320 KB Output is correct
16 Correct 969 ms 105688 KB Output is correct
17 Correct 948 ms 103076 KB Output is correct
18 Correct 599 ms 4116 KB Output is correct
19 Correct 2485 ms 403380 KB Output is correct
20 Correct 2630 ms 403368 KB Output is correct
21 Correct 2404 ms 403352 KB Output is correct
22 Correct 779 ms 102520 KB Output is correct
23 Correct 897 ms 107060 KB Output is correct
24 Correct 547 ms 4060 KB Output is correct

Subtask #4
0 / 57.0

# 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 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 121 ms 50968 KB Output is correct
8 Correct 107 ms 51020 KB Output is correct
9 Correct 122 ms 50968 KB Output is correct
10 Correct 79 ms 26224 KB Output is correct
11 Correct 69 ms 25156 KB Output is correct
12 Correct 20 ms 504 KB Output is correct
13 Correct 107 ms 51040 KB Output is correct
14 Correct 106 ms 50996 KB Output is correct
15 Correct 107 ms 50996 KB Output is correct
16 Correct 67 ms 25160 KB Output is correct
17 Correct 68 ms 26196 KB Output is correct
18 Correct 18 ms 504 KB Output is correct
19 Correct 2673 ms 401476 KB Output is correct
20 Correct 2782 ms 401560 KB Output is correct
21 Correct 2706 ms 401532 KB Output is correct
22 Correct 1097 ms 104224 KB Output is correct
23 Correct 954 ms 101332 KB Output is correct
24 Correct 591 ms 3936 KB Output is correct
25 Correct 2623 ms 401344 KB Output is correct
26 Correct 2596 ms 401616 KB Output is correct
27 Correct 2479 ms 401484 KB Output is correct
28 Correct 783 ms 101408 KB Output is correct
29 Correct 894 ms 106384 KB Output is correct
30 Correct 528 ms 3276 KB Output is correct
31 Correct 2545 ms 403628 KB Output is correct
32 Correct 2708 ms 402032 KB Output is correct
33 Correct 2722 ms 402320 KB Output is correct
34 Correct 969 ms 105688 KB Output is correct
35 Correct 948 ms 103076 KB Output is correct
36 Correct 599 ms 4116 KB Output is correct
37 Correct 2485 ms 403380 KB Output is correct
38 Correct 2630 ms 403368 KB Output is correct
39 Correct 2404 ms 403352 KB Output is correct
40 Correct 779 ms 102520 KB Output is correct
41 Correct 897 ms 107060 KB Output is correct
42 Correct 547 ms 4060 KB Output is correct
43 Execution timed out 3160 ms 1029048 KB Time limit exceeded
44 Halted 0 ms 0 KB -