oj.uz

Submission #152438

# Submission time Handle Problem Language Result Execution time Memory
152438 2019-09-08T02:30:52 Z cheetose Examination (JOI19_examination) C++11
41 / 100
 2972 ms 403512 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)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:171: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:173: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:177: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
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 3 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 113 ms 50972 KB Output is correct
8 Correct 110 ms 51040 KB Output is correct
9 Correct 109 ms 50996 KB Output is correct
10 Correct 77 ms 26196 KB Output is correct
11 Correct 70 ms 25160 KB Output is correct
12 Correct 20 ms 504 KB Output is correct
13 Correct 110 ms 50996 KB Output is correct
14 Correct 110 ms 50996 KB Output is correct
15 Correct 109 ms 50996 KB Output is correct
16 Correct 68 ms 25160 KB Output is correct
17 Correct 71 ms 26468 KB Output is correct
18 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2940 ms 401428 KB Output is correct
2 Correct 2796 ms 401656 KB Output is correct
3 Correct 2782 ms 401508 KB Output is correct
4 Correct 1106 ms 104272 KB Output is correct
5 Correct 977 ms 101368 KB Output is correct
6 Correct 598 ms 3900 KB Output is correct
7 Correct 2802 ms 401404 KB Output is correct
8 Correct 2972 ms 401448 KB Output is correct
9 Correct 2605 ms 401832 KB Output is correct
10 Correct 789 ms 102040 KB Output is correct
11 Correct 928 ms 107360 KB Output is correct
12 Correct 524 ms 4316 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2940 ms 401428 KB Output is correct
2 Correct 2796 ms 401656 KB Output is correct
3 Correct 2782 ms 401508 KB Output is correct
4 Correct 1106 ms 104272 KB Output is correct
5 Correct 977 ms 101368 KB Output is correct
6 Correct 598 ms 3900 KB Output is correct
7 Correct 2802 ms 401404 KB Output is correct
8 Correct 2972 ms 401448 KB Output is correct
9 Correct 2605 ms 401832 KB Output is correct
10 Correct 789 ms 102040 KB Output is correct
11 Correct 928 ms 107360 KB Output is correct
12 Correct 524 ms 4316 KB Output is correct
13 Correct 2717 ms 403512 KB Output is correct
14 Correct 2947 ms 402556 KB Output is correct
15 Correct 2705 ms 403056 KB Output is correct
16 Correct 974 ms 105904 KB Output is correct
17 Correct 952 ms 103112 KB Output is correct
18 Correct 603 ms 4728 KB Output is correct
19 Correct 2638 ms 403240 KB Output is correct
20 Correct 2672 ms 403336 KB Output is correct
21 Correct 2375 ms 403368 KB Output is correct
22 Correct 786 ms 102644 KB Output is correct
23 Correct 906 ms 107232 KB Output is correct
24 Correct 520 ms 4224 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 3 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 113 ms 50972 KB Output is correct
8 Correct 110 ms 51040 KB Output is correct
9 Correct 109 ms 50996 KB Output is correct
10 Correct 77 ms 26196 KB Output is correct
11 Correct 70 ms 25160 KB Output is correct
12 Correct 20 ms 504 KB Output is correct
13 Correct 110 ms 50996 KB Output is correct
14 Correct 110 ms 50996 KB Output is correct
15 Correct 109 ms 50996 KB Output is correct
16 Correct 68 ms 25160 KB Output is correct
17 Correct 71 ms 26468 KB Output is correct
18 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)