oj.uz

Submission #104486

# Submission time Handle Problem Language Result Execution time Memory
104486 2019-04-07T06:34:38 Z psmao Examination (JOI19_examination) C++14
0 / 100
 696 ms 22740 KB 
#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<pii,int> sammi;
map<pair<int,pii>,int> sammi2;
int tag[maxn];

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) 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, sammi[mp(a[i].x,a[i].y)]);
			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;
}

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)] ++;
	}
	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

examination.cpp: In function 'void CDQ(int, int)':
examination.cpp:59: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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 12 ms 1024 KB Output is correct
8 Correct 15 ms 1016 KB Output is correct
9 Correct 13 ms 1024 KB Output is correct
10 Correct 11 ms 1024 KB Output is correct
11 Correct 11 ms 1024 KB Output is correct
12 Incorrect 6 ms 640 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 21920 KB Output is correct
2 Correct 629 ms 21916 KB Output is correct
3 Correct 691 ms 21880 KB Output is correct
4 Correct 534 ms 21016 KB Output is correct
5 Correct 503 ms 22740 KB Output is correct
6 Incorrect 54 ms 2324 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 21920 KB Output is correct
2 Correct 629 ms 21916 KB Output is correct
3 Correct 691 ms 21880 KB Output is correct
4 Correct 534 ms 21016 KB Output is correct
5 Correct 503 ms 22740 KB Output is correct
6 Incorrect 54 ms 2324 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 12 ms 1024 KB Output is correct
8 Correct 15 ms 1016 KB Output is correct
9 Correct 13 ms 1024 KB Output is correct
10 Correct 11 ms 1024 KB Output is correct
11 Correct 11 ms 1024 KB Output is correct
12 Incorrect 6 ms 640 KB Output isn't correct
13 Halted 0 ms 0 KB -