Submission #104578

#	Time	Username	Problem	Language	Result	Execution time	Memory
104578		psmao	Examination (JOI19_examination)	C++14	100 / 100	2308 ms	24452 KiB

examination

#include <bits/stdc++.h>
using namespace std;
 
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;
 
void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 100050;

struct pts{int x, y, z, _type;}a[maxn*2], tmp[maxn<<1];
int n, Q, Ans[maxn], bit[maxn*2], tot, disc[maxn*2], T, tim[2*maxn];
map<pair<int,pii>,pii> sammi;
int tag[maxn];
int restore[maxn<<1];

void add(int p, int v)
{
	for(int i = p; i <= tot; i += i&-i)
	{
		if(tim[i] != T) {tim[i] = T; bit[i] = 0;}
		bit[i] += v;
	}
}
int ask(int p)
{
	int ret = 0;
	for(int i = p; i; i -= i&-i)
		if(tim[i] == T) ret += bit[i];
	return ret;
}
void CDQ(int l, int r)
{
	if(l == r) 
	{
		Ans[sammi[mp(a[l].x,mp(a[l].y,restore[a[l].z]))].se] += sammi[mp(a[l].x,mp(a[l].y,restore[a[l].z]))].fi;
		return;
	}
	int mid = l + r >> 1;
	CDQ(l, mid); CDQ(mid+1, r);
	int i = l, j = mid + 1, top = 0;
	++ T;
	while(i <= mid || j <= r)
	{
		if(j > r || (i <= mid && a[i].y >= a[j].y))
		{
			add(a[i].z, sammi[mp(a[i].x,mp(a[i].y,restore[a[i].z]))].fi);
			tmp[++top] = a[i++];
		}
		else
		{
			Ans[sammi[mp(a[j].x,mp(a[j].y,restore[a[j].z]))].se] += ask(tot) - ask(a[j].z-1);
			tmp[++top] = a[j++];
		}
	}
	fo(i,1,top) a[l+i-1] = tmp[i];
}
bool cmp(pts a, pts b)
{
    if(a.x != b.x) return a.x > b.x;
    if(a.y != b.y) return a.y > b.y;
    return a.z > b.z;
}

int main()
{
	sf("%d%d",&n,&Q);
	int o = 0;
	fo(i,1,n)
	{
		int x, y;
		sf("%d%d",&x,&y);
		if(!sammi.count(mp(x,mp(y,x+y))))
			a[++o] = (struct pts){x, y, x + y, 0};
		sammi[mp(x,mp(y,x+y))].fi ++;
	}
	fo(i,1,Q)
	{
		int x, y, z;
		sf("%d%d%d",&x,&y,&z);
		if(!sammi.count(mp(x,mp(y,z))))
		{
			a[++o] = (struct pts){x, y, z, i};		
			sammi[mp(x,mp(y,z))].se = i;
		}
		else if(sammi[mp(x,mp(y,z))].se == 0)
		{
			sammi[mp(x,mp(y,z))].se = i;
		}
		tag[i] = sammi[mp(x,mp(y,z))].se;
	}
	n = o;

	sort(a+1,a+n+1,cmp);
	//discretization
	fo(i,1,n) disc[++tot] = a[i].z;
	sort(disc+1,disc+tot+1);
	tot = unique(disc+1,disc+tot+1)-(disc+1);
	fo(i,1,n) 
	{
		int x = a[i].z;
		a[i].z = lower_bound(disc+1,disc+tot+1,a[i].z)-disc;
		restore[a[i].z] = x;
	}
	//cdq divide and conquer 
// 	return 0;
	CDQ(1, n);
	fo(i,1,Q) pf("%d\n",Ans[tag[i]]);
	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void CDQ(int, int)':
examination.cpp:63:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
examination.cpp: In function 'int main()':
examination.cpp:91:4: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  sf("%d%d",&n,&Q);
    ^
examination.cpp:96:5: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   sf("%d%d",&x,&y);
     ^
examination.cpp:104:5: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   sf("%d%d%d",&x,&y,&z);
     ^

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57