oj.uz

Submission #88409

# Submission time Handle Problem Language Result Execution time Memory
88409 2018-12-05T16:12:45 Z Pajaraja Jousting tournament (IOI12_tournament) C++17
0 / 100
 45 ms 4392 KB 
#include <bits/stdc++.h>
using namespace std;
int seg[2][400028],bag[2][400028],segmax[400028],k[100007],s[100007],e[100007],p[100007],q[100007];
void relax(int ind,int k)
{
	bag[k][2*ind]+=bag[k][ind];
	bag[k][2*ind+1]+=bag[k][ind];
	bag[k][ind]=0;
}
void upd(int l,int r,int lt,int rt,int val,int k,int ind)
{
	if(l>=lt && r<=rt)
	{
		bag[k][ind]+=val;
		return;
	}
	if(r<lt || l>rt) return;
	int s=(l+r)/2;
	upd(l,s,lt,rt,val,k,2*ind);
	upd(s+1,r,lt,rt,val,k,2*ind+1);
}
int val(int l,int r,int poz,int k,int ind)
{
	if(l==r) return bag[k][ind];
	relax(ind,k);
	int s=(l+r)/2;
	if(poz<=s) return val(l,s,poz,k,2*ind);
	return val(s+1,r,poz,k,2*ind+1);
}
int find(int l,int r,int lt,int rt,int ind)
{
	if(l>=lt && r<=rt) return segmax[ind];
	if(r<lt || l>rt) return -1;
	int s=(l+r)/2;
	return fmax(find(l,s,lt,rt,2*ind),find(s+1,r,lt,rt,2*ind+1));
}
void make(int l,int r,int ind)
{
	if(l==r)
	{
		segmax[ind]=k[l];
		return;
	}
	int s=(l+r)/2;
	make(l,s,2*ind);
	make(s+1,r,2*ind+1);
	segmax[ind]=fmax(segmax[2*ind],segmax[2*ind+1]);
}
int GetBestPosition(int N,int C,int R,int K[] ,int S[],int E[])
{
	int n=N,c=C,r=R;
	for(int i=0;i<n-1;i++) k[i]=K[i];
	for(int i=0;i<c;i++) s[i]=S[i];
	for(int i=0;i<c;i++) e[i]=E[i];
	make(0,n-2,1);
	for(int i=0;i<c;i++)
	{
		int a=s[i]+val(0,n,s[i],0,1),b=e[i]+val(0,n,e[i],1,1);
		upd(0,n,a+1,n,e[i]-s[i],0,1);
		upd(0,n,a,n,e[i]-s[i],1,1);
		s[i]=a;
		e[i]=b;
	}
	for(int i=0;i<c;i++) if(find(0,n-2,s[i],e[i]-1,1)<r)
	{
		p[s[i]]++;
		q[e[i]]++;
	}
	int cur=0,max=0,maxind=0;
	for(int i=0;i<n;i++)
	{
		cur+=p[i];
		if(cur>max)
		{
			max=cur;
			maxind=i;
		}
		cur-=q[i];
	}
	return maxind;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Incorrect 2 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 4392 KB Output isn't correct
2 Halted 0 ms 0 KB -