oj.uz

Submission #104578

# Submission time Handle Problem Language Result Execution time Memory
104578 2019-04-08T06:39:24 Z psmao Examination (JOI19_examination) C++14
100 / 100
 2308 ms 24452 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<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

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.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 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 25 ms 1152 KB Output is correct
8 Correct 20 ms 1024 KB Output is correct
9 Correct 22 ms 1152 KB Output is correct
10 Correct 21 ms 1024 KB Output is correct
11 Correct 23 ms 1024 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 20 ms 1152 KB Output is correct
14 Correct 19 ms 1152 KB Output is correct
15 Correct 20 ms 1152 KB Output is correct
16 Correct 17 ms 1060 KB Output is correct
17 Correct 18 ms 1152 KB Output is correct
18 Correct 5 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1777 ms 22220 KB Output is correct
2 Correct 1779 ms 22264 KB Output is correct
3 Correct 1705 ms 22220 KB Output is correct
4 Correct 1432 ms 21388 KB Output is correct
5 Correct 1055 ms 21232 KB Output is correct
6 Correct 57 ms 1400 KB Output is correct
7 Correct 1645 ms 22712 KB Output is correct
8 Correct 1859 ms 22724 KB Output is correct
9 Correct 1677 ms 22828 KB Output is correct
10 Correct 865 ms 16760 KB Output is correct
11 Correct 870 ms 16720 KB Output is correct
12 Correct 48 ms 1400 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1777 ms 22220 KB Output is correct
2 Correct 1779 ms 22264 KB Output is correct
3 Correct 1705 ms 22220 KB Output is correct
4 Correct 1432 ms 21388 KB Output is correct
5 Correct 1055 ms 21232 KB Output is correct
6 Correct 57 ms 1400 KB Output is correct
7 Correct 1645 ms 22712 KB Output is correct
8 Correct 1859 ms 22724 KB Output is correct
9 Correct 1677 ms 22828 KB Output is correct
10 Correct 865 ms 16760 KB Output is correct
11 Correct 870 ms 16720 KB Output is correct
12 Correct 48 ms 1400 KB Output is correct
13 Correct 2169 ms 23416 KB Output is correct
14 Correct 2020 ms 23164 KB Output is correct
15 Correct 1756 ms 22780 KB Output is correct
16 Correct 1599 ms 22148 KB Output is correct
17 Correct 1281 ms 22264 KB Output is correct
18 Correct 105 ms 1912 KB Output is correct
19 Correct 1967 ms 23160 KB Output is correct
20 Correct 1873 ms 23312 KB Output is correct
21 Correct 2089 ms 23544 KB Output is correct
22 Correct 839 ms 16648 KB Output is correct
23 Correct 925 ms 16608 KB Output is correct
24 Correct 56 ms 1528 KB Output is correct

Subtask #4
57.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 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 25 ms 1152 KB Output is correct
8 Correct 20 ms 1024 KB Output is correct
9 Correct 22 ms 1152 KB Output is correct
10 Correct 21 ms 1024 KB Output is correct
11 Correct 23 ms 1024 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 20 ms 1152 KB Output is correct
14 Correct 19 ms 1152 KB Output is correct
15 Correct 20 ms 1152 KB Output is correct
16 Correct 17 ms 1060 KB Output is correct
17 Correct 18 ms 1152 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 1777 ms 22220 KB Output is correct
20 Correct 1779 ms 22264 KB Output is correct
21 Correct 1705 ms 22220 KB Output is correct
22 Correct 1432 ms 21388 KB Output is correct
23 Correct 1055 ms 21232 KB Output is correct
24 Correct 57 ms 1400 KB Output is correct
25 Correct 1645 ms 22712 KB Output is correct
26 Correct 1859 ms 22724 KB Output is correct
27 Correct 1677 ms 22828 KB Output is correct
28 Correct 865 ms 16760 KB Output is correct
29 Correct 870 ms 16720 KB Output is correct
30 Correct 48 ms 1400 KB Output is correct
31 Correct 2169 ms 23416 KB Output is correct
32 Correct 2020 ms 23164 KB Output is correct
33 Correct 1756 ms 22780 KB Output is correct
34 Correct 1599 ms 22148 KB Output is correct
35 Correct 1281 ms 22264 KB Output is correct
36 Correct 105 ms 1912 KB Output is correct
37 Correct 1967 ms 23160 KB Output is correct
38 Correct 1873 ms 23312 KB Output is correct
39 Correct 2089 ms 23544 KB Output is correct
40 Correct 839 ms 16648 KB Output is correct
41 Correct 925 ms 16608 KB Output is correct
42 Correct 56 ms 1528 KB Output is correct
43 Correct 2109 ms 24112 KB Output is correct
44 Correct 2308 ms 24064 KB Output is correct
45 Correct 2208 ms 24200 KB Output is correct
46 Correct 1805 ms 24072 KB Output is correct
47 Correct 1476 ms 24328 KB Output is correct
48 Correct 119 ms 2292 KB Output is correct
49 Correct 2210 ms 24452 KB Output is correct
50 Correct 2191 ms 24188 KB Output is correct
51 Correct 1980 ms 24316 KB Output is correct
52 Correct 1442 ms 24080 KB Output is correct
53 Correct 1145 ms 22996 KB Output is correct