oj.uz

Submission #201487

# Submission time Handle Problem Language Result Execution time Memory
201487 2020-02-10T17:40:28 Z arnold518 Teams (IOI15_teams) C++14
100 / 100
 2356 ms 410632 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;

struct Point
{
	int X, Y;
	bool operator < (const Point &p) const { return pii(X, Y)<pii(p.X, p.Y); }
};

struct Node
{
	int val;
	Node *lc, *rc;
	Node() : lc(NULL), rc(NULL), val(0) {}
};

Node *tree[MAXN+10], *temp;

int N;
Point A[MAXN+10], B[MAXN+10];
int xval[MAXN+10], yval[MAXN+10];
int xcomp[MAXN+10], ycomp[MAXN+10];

void makeTree(Node *node, int tl, int tr)
{
	if(tl==tr) return;
	int mid=tl+tr>>1;
	node->lc=new Node();
	node->rc=new Node();
	makeTree(node->lc, tl, mid);
	makeTree(node->rc, mid+1, tr);
}

Node *addTree(Node *node, int tl, int tr, int pos)
{
	if(pos<tl || tr<pos) return node;
	Node *ret=new Node();
	if(tl==tr)
	{
		ret->val=node->val+1;
		return ret;
	}
	int mid=tl+tr>>1;
	ret->lc=addTree(node->lc, tl, mid, pos);
	ret->rc=addTree(node->rc, mid+1, tr, pos);
	ret->val=ret->lc->val+ret->rc->val;
	return ret;
}

int query(Node *nodel, Node *noder, Node *nodet, int tl, int tr, int l, int r)
{
	if(l<=tl && tr<=r) return nodet->val=noder->val-nodel->val;
	if(r<tl || tr<l) return nodet->val=0;
	int mid=tl+tr>>1;
	return nodet->val=query(nodel->lc, noder->lc, nodet->lc, tl, mid, l, r)+query(nodel->rc, noder->rc, nodet->rc, mid+1, tr, l, r);
}

int query(int xl, int xr, int yl, int yr)
{
	return query(tree[xl], tree[xr], temp, 0, N+1, yl, yr);
}

int query2(Node *nodel, Node *noder, Node *nodet, int tl, int tr, int l, int r, int k)
{
	if(tl==tr) return tl;
	if(l<=tl && tr<=r) { nodet->lc->val=noder->lc->val-nodel->lc->val; nodet->rc->val=noder->rc->val-nodel->rc->val; }
	int mid=tl+tr>>1;
	if(nodet->lc->val<k) return query2(nodel->rc, noder->rc, nodet->rc, mid+1, tr, l, r, k-nodet->lc->val);
	else return query2(nodel->lc, noder->lc, nodet->lc, tl, mid, l, r, k);
}

int query2(int xl, int xr, int yl, int yr, int k)
{
	query(xl, xr, yl, yr);
	return query2(tree[xl], tree[xr], temp, 0, N+1, yl, yr, k);
}

int M, K[MAXN+10];

void init(int _N, int _A[], int _B[])
{
	int i, j;
	N=_N; for(i=1; i<=N; i++) A[i]={_A[i-1], _B[i-1]};
	sort(A+1, A+N+1);

	vector<pii> V;
	for(i=1; i<=N; i++) V.push_back({A[i].Y, i});
	sort(V.begin(), V.end());
	for(i=0; i<V.size(); i++) B[V[i].second].Y=i+1; 
	for(i=1; i<=N; i++) B[i].X=i;

	tree[0]=new Node();
	makeTree(tree[0], 0, N+1);
	for(i=1; i<=N; i++) tree[i]=addTree(tree[i-1], 0, N+1, B[i].Y);

	for(i=1; i<=N; i++) xval[B[i].X]=A[i].X;
	for(i=1; i<=N; i++) yval[B[i].Y]=A[i].Y;
	for(i=1; i<=N; i++) xcomp[i]=upper_bound(xval+1, xval+N+1, i)-xval-1;
	for(i=1; i<=N; i++) ycomp[i]=lower_bound(yval+1, yval+N+1, i)-yval;

	temp=new Node();
	makeTree(temp, 0, N+1);
}

int can(int _M, int _K[])
{
	int i, j;
	M=_M; for(i=1; i<=M; i++) K[i]=_K[i-1];
	sort(K+1, K+M+1);

	vector<Point> S;
	S.push_back({0, N+1});
	for(i=1; i<=M; i++)
	{
		int todo=K[i];
		Point now={xcomp[K[i]], ycomp[K[i]]};
		while(!S.empty() && S.back().Y<now.Y) S.pop_back();
		while(1)
		{
			if(S.empty()) return 0;
			Point T=S.back();
			int p=min(T.Y, query2(T.X, now.X, now.Y, T.Y, todo));
			todo-=query(T.X, now.X, now.Y, p);
			//printf("!%d / %d %d / %d %d\n", p, now.X, now.Y, T.X, T.Y);
			if(todo==0)
			{
				if(p==T.Y) S.pop_back();
				S.push_back({now.X, p});
				break;
			}
			now.Y=T.Y+1;
			S.pop_back();
		}
	}
	return 1;
}

Compilation message

teams.cpp: In constructor 'Node::Node()':
teams.cpp:20:13: warning: 'Node::rc' will be initialized after [-Wreorder]
  Node *lc, *rc;
             ^~
teams.cpp:19:6: warning:   'int Node::val' [-Wreorder]
  int val;
      ^~~
teams.cpp:21:2: warning:   when initialized here [-Wreorder]
  Node() : lc(NULL), rc(NULL), val(0) {}
  ^~~~
teams.cpp: In function 'void makeTree(Node*, int, int)':
teams.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
teams.cpp: In function 'Node* addTree(Node*, int, int, int)':
teams.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
teams.cpp: In function 'int query(Node*, Node*, Node*, int, int, int, int)':
teams.cpp:61:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
teams.cpp: In function 'int query2(Node*, Node*, Node*, int, int, int, int, int)':
teams.cpp:74:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:96:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size(); i++) B[V[i].second].Y=i+1; 
           ~^~~~~~~~~
teams.cpp:105:68: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  for(i=1; i<=N; i++) xcomp[i]=upper_bound(xval+1, xval+N+1, i)-xval-1;
                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:106:63: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  for(i=1; i<=N; i++) ycomp[i]=lower_bound(yval+1, yval+N+1, i)-yval;
                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
teams.cpp:89:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:114:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 380 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 7 ms 376 KB Output is correct
13 Correct 6 ms 380 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 6 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 6 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 6 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 73836 KB Output is correct
2 Correct 184 ms 73964 KB Output is correct
3 Correct 185 ms 74092 KB Output is correct
4 Correct 183 ms 73940 KB Output is correct
5 Correct 130 ms 73964 KB Output is correct
6 Correct 131 ms 73944 KB Output is correct
7 Correct 128 ms 73964 KB Output is correct
8 Correct 127 ms 73964 KB Output is correct
9 Correct 189 ms 73964 KB Output is correct
10 Correct 151 ms 73968 KB Output is correct
11 Correct 140 ms 74156 KB Output is correct
12 Correct 145 ms 74096 KB Output is correct
13 Correct 139 ms 74220 KB Output is correct
14 Correct 147 ms 74092 KB Output is correct
15 Correct 177 ms 74220 KB Output is correct
16 Correct 169 ms 74128 KB Output is correct
17 Correct 137 ms 74224 KB Output is correct
18 Correct 132 ms 74348 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 73836 KB Output is correct
2 Correct 192 ms 73968 KB Output is correct
3 Correct 502 ms 76548 KB Output is correct
4 Correct 181 ms 73964 KB Output is correct
5 Correct 235 ms 73964 KB Output is correct
6 Correct 220 ms 73964 KB Output is correct
7 Correct 134 ms 73964 KB Output is correct
8 Correct 205 ms 73964 KB Output is correct
9 Correct 187 ms 73964 KB Output is correct
10 Correct 291 ms 73964 KB Output is correct
11 Correct 361 ms 74092 KB Output is correct
12 Correct 398 ms 74092 KB Output is correct
13 Correct 529 ms 74092 KB Output is correct
14 Correct 590 ms 75352 KB Output is correct
15 Correct 266 ms 74092 KB Output is correct
16 Correct 268 ms 74092 KB Output is correct
17 Correct 215 ms 74092 KB Output is correct
18 Correct 240 ms 74092 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1341 ms 402688 KB Output is correct
2 Correct 1188 ms 403040 KB Output is correct
3 Correct 2155 ms 406160 KB Output is correct
4 Correct 1188 ms 403044 KB Output is correct
5 Correct 1301 ms 402784 KB Output is correct
6 Correct 1231 ms 402912 KB Output is correct
7 Correct 702 ms 402784 KB Output is correct
8 Correct 1120 ms 402784 KB Output is correct
9 Correct 990 ms 402772 KB Output is correct
10 Correct 1119 ms 402852 KB Output is correct
11 Correct 1343 ms 405856 KB Output is correct
12 Correct 1471 ms 406524 KB Output is correct
13 Correct 2086 ms 408024 KB Output is correct
14 Correct 2356 ms 410632 KB Output is correct
15 Correct 1234 ms 409312 KB Output is correct
16 Correct 1218 ms 409568 KB Output is correct
17 Correct 971 ms 408708 KB Output is correct
18 Correct 965 ms 408800 KB Output is correct