oj.uz

Submission #152436

# Submission time Handle Problem Language Result Execution time Memory
152436 2019-09-08T02:26:58 Z cheetose Examination (JOI19_examination) C++11
41 / 100
 2989 ms 404872 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)xtree[node].yroot=yinit();
	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:167: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:169: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:173: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 248 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 2 ms 632 KB Output is correct
7 Correct 110 ms 50996 KB Output is correct
8 Correct 120 ms 50980 KB Output is correct
9 Correct 112 ms 50996 KB Output is correct
10 Correct 72 ms 26196 KB Output is correct
11 Correct 72 ms 25288 KB Output is correct
12 Correct 20 ms 508 KB Output is correct
13 Correct 109 ms 51124 KB Output is correct
14 Correct 111 ms 51128 KB Output is correct
15 Correct 115 ms 51156 KB Output is correct
16 Correct 69 ms 25292 KB Output is correct
17 Correct 70 ms 26324 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 2989 ms 401484 KB Output is correct
2 Correct 2887 ms 404092 KB Output is correct
3 Correct 2818 ms 404036 KB Output is correct
4 Correct 1101 ms 106024 KB Output is correct
5 Correct 961 ms 103164 KB Output is correct
6 Correct 594 ms 4708 KB Output is correct
7 Correct 2783 ms 404004 KB Output is correct
8 Correct 2753 ms 403972 KB Output is correct
9 Correct 2520 ms 403840 KB Output is correct
10 Correct 809 ms 103084 KB Output is correct
11 Correct 947 ms 107752 KB Output is correct
12 Correct 525 ms 4264 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2989 ms 401484 KB Output is correct
2 Correct 2887 ms 404092 KB Output is correct
3 Correct 2818 ms 404036 KB Output is correct
4 Correct 1101 ms 106024 KB Output is correct
5 Correct 961 ms 103164 KB Output is correct
6 Correct 594 ms 4708 KB Output is correct
7 Correct 2783 ms 404004 KB Output is correct
8 Correct 2753 ms 403972 KB Output is correct
9 Correct 2520 ms 403840 KB Output is correct
10 Correct 809 ms 103084 KB Output is correct
11 Correct 947 ms 107752 KB Output is correct
12 Correct 525 ms 4264 KB Output is correct
13 Correct 2642 ms 404824 KB Output is correct
14 Correct 2780 ms 404652 KB Output is correct
15 Correct 2739 ms 403972 KB Output is correct
16 Correct 964 ms 106724 KB Output is correct
17 Correct 985 ms 103932 KB Output is correct
18 Correct 604 ms 4856 KB Output is correct
19 Correct 2611 ms 404828 KB Output is correct
20 Correct 2815 ms 404872 KB Output is correct
21 Correct 2552 ms 404800 KB Output is correct
22 Correct 789 ms 103092 KB Output is correct
23 Correct 897 ms 107648 KB Output is correct
24 Correct 524 ms 4472 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 248 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 2 ms 632 KB Output is correct
7 Correct 110 ms 50996 KB Output is correct
8 Correct 120 ms 50980 KB Output is correct
9 Correct 112 ms 50996 KB Output is correct
10 Correct 72 ms 26196 KB Output is correct
11 Correct 72 ms 25288 KB Output is correct
12 Correct 20 ms 508 KB Output is correct
13 Correct 109 ms 51124 KB Output is correct
14 Correct 111 ms 51128 KB Output is correct
15 Correct 115 ms 51156 KB Output is correct
16 Correct 69 ms 25292 KB Output is correct
17 Correct 70 ms 26324 KB Output is correct
18 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)