Submission #201487

#	Time	Username	Problem	Language	Result	Execution time	Memory
201487		arnold518	Teams (IOI15_teams)	C++14	100 / 100	2356 ms	410632 KiB

teams

#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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23