Submission #946012

#	Time	Username	Problem	Language	Result	Execution time	Memory
946012		teacup	Jousting tournament (IOI12_tournament)	C++17	100 / 100	348 ms	45108 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
typedef vector<int> vi;
#define iii tuple<int,int,int>
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef map<int,int> mii;
struct node{
	int32_t s,e;
	int mn,mx,sum,add_val,set_val;
	bool lset;
	node *l, *r;
	node (int _s, int _e, int A[]=NULL): s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL){
		if (A==NULL) return;
		if (s==e) mn=mx=sum=A[s];
		else{
			l=new node(s, (s+e)>>1,A), r=new node((s+e+2)>>1,e,A);
			combine();
		}
	}
	void create_children(){
		if (s==e) return;
		if (l!=NULL) return;
		int m=(s+e)>>1;
		l=new node(s,m);
		r=new node(m+1,e);
	}
	void self_set(int v){
		lset=1;
		mn=mx=set_val=v;
		sum=v*(e-s+1);
		add_val=0;
	}
	void self_add(int v){
		if (lset) {self_set(v+set_val); return;}
		mn+=v, mx+=v, add_val+=v;
		sum+=v*(e-s+1);
	}
	void lazy(){
		if (s==e) return;
		if (lset){
			l->self_set(set_val), r->self_set(set_val);
			set_val=0; lset=0;
		}
		if (add_val!=0){
			l->self_add(add_val), r->self_add(add_val);
			add_val=0;
		}
	}
	void combine(){
		if (l==NULL) return;
		sum=l->sum +r->sum;
		mn=min(l->mn,r->mn);
		mx=max(l->mx,r->mx);
	}
	#define UPDATE(name)\
	void name(int x, int y, int v){\
		if (s==x&&e==y) {self_##name(v); return;}\
		int m=(s+e)>>1; \
		create_children(); lazy();\
		if (x<=m) l->name(x,min(y,m),v);\
		if (y>m) r->name(max(x,m+1),y,v);\
		combine();\
	}
	UPDATE(add)
	UPDATE(set)
	#define QUERY(name,fn,var,lazyfn)\
	int range_##name(int x, int y){\
		if (s==x&&e==y) return var;\
		if (l==NULL||lset) return lazyfn(var);\
		int m=(s+e)>>1; lazy();\
		if (y<=m) return l->range_##name(x,y);\
		if (x>m) return r->range_##name(x,y);\
		return fn(l->range_##name(x,m), r->range_##name(m+1,y));\
	}
	#define SAME(var) (var)
	#define PART(var) ((var)/(e-s+1)*(y-x+1))
	#define SUM(a,b) ((a)+(b))
	QUERY(min,min,mn,SAME)
	QUERY(max,max,mx,SAME)
	QUERY(sum,SUM,sum,PART)
	~node(){
		if (l!=NULL) delete l;
		if (r!=NULL) delete r;
	}
}*ranks, *alive, *wins;

int32_t GetBestPosition(int32_t N, int32_t C, int32_t R, int32_t *K, int32_t *S, int32_t *E){
	ranks = new node(0,N+5);
	alive = new node(0,N+5);
	wins = new node(0,N+5);
	for (int32_t i=0; i<N-1; i++) ranks->set(i, i, K[i]);
	alive->set(0,N,1);
	for (int32_t i=0; i<C; i++){
		int32_t l=0,r=N-1, actualS, actualE;
		while (l<r){
			int32_t m = (l+r)/2;
			if (alive->range_sum(0,m)<=S[i]) l=m+1;
			else r=m;
		}
		actualS = l;
		l=0; r=N-1;
		while (l<r){
			int32_t m = (l+r)/2;
			if (alive->range_sum(0,m)<=E[i]+1) l=m+1;
			else r=m;
		}
		actualE = l-1;
		
		alive->set(actualS,actualS,1);
		alive->set(actualS+1,actualE,0);
		if (ranks->range_max(actualS, actualE-1) < R){
			wins->add(actualS,actualE,1);
		}
	}
	int32_t maxPos=0, maxWins=0;
	for (int32_t i=0; i<N; i++){
		int32_t currWins = wins->range_max(i,i);
		if (currWins > maxWins){
			maxWins = currWins;
			maxPos = i;
		}
	}
	return maxPos;
}

Compilation message (stderr)

tournament.cpp: In constructor 'node::node(long long int, long long int, long long int*)':
tournament.cpp:13:7: warning: 'node::lset' will be initialized after [-Wreorder]
   13 |  bool lset;
      |       ^~~~
tournament.cpp:12:16: warning:   'long long int node::add_val' [-Wreorder]
   12 |  int mn,mx,sum,add_val,set_val;
      |                ^~~~~~~
tournament.cpp:15:2: warning:   when initialized here [-Wreorder]
   15 |  node (int _s, int _e, int A[]=NULL): s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL){
      |  ^~~~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51