Submission #104485

#	Time	Username	Problem	Language	Result	Execution time	Memory
104485		psmao	Examination (JOI19_examination)	C++14	0 / 100	414 ms	24368 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];

void add(int p)
{
	for(int i = p; i <= tot; i += i&-i)
	{
		if(tim[i] != T) {tim[i] = T; bit[i] = 0;}
		++ bit[i];
	}
}
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) 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))
		{
			if(a[i]._type == 0) add(a[i].z);
			tmp[++top] = a[i++];
		}
		else
		{
			if(a[j]._type != 0) Ans[a[j]._type] += 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;
}
map<pii,bool> sammi;
map<pair<int,pii>,int> sammi2;
int tag[maxn];

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,y)))
			a[++o] = (struct pts){x, y, x + y, 0};
		sammi[mp(x,y)] = true;
	}
	fo(i,1,Q)
	{
		int x, y, z;
		sf("%d%d%d",&x,&y,&z);
		if(!sammi2.count(mp(x,mp(y,z))))
		{
			a[++o] = (struct pts){x, y, z, i};		
			sammi2[mp(x,mp(y,z))] = i;
		}
		tag[i] = sammi2[mp(x,mp(y,z))];
	}
	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) a[i].z = lower_bound(disc+1,disc+tot+1,a[i].z)-disc;
	//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:56:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
examination.cpp: In function 'int main()':
examination.cpp:87: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:92: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:100: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: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57