oj.uz

Submission #121907

# Submission time Handle Problem Language Result Execution time Memory
121907 2019-06-27T07:48:49 Z baluteshih Jousting tournament (IOI12_tournament) C++14
100 / 100
 103 ms 12160 KB 
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int seg[400005],lazy[400005],cnt[100005];
vector<pii> oper[100005];
pii rel[100005];

void build(int l,int r,int rt)
{
	if(l==r)
		return seg[rt]=1,void();
	int m=l+r>>1;
	build(l,m,rt<<1),build(m+1,r,rt<<1|1);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

void down(int rt)
{
	if(!lazy[rt]) return;
	seg[rt<<1]=seg[rt<<1|1]=0,lazy[rt<<1]=lazy[rt<<1|1]=1;
	lazy[rt]=0;
}

void modify(int L,int R,int l,int r,int rt)
{
	if(l!=r) down(rt);
	if(L<=l&&R>=r)
		return seg[rt]=0,lazy[rt]=1,void();
	int m=l+r>>1;
	if(L<=m) modify(L,R,l,m,rt<<1);
	if(R>m) modify(L,R,m+1,r,rt<<1|1);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

int query(int x,int l,int r,int rt)
{
	if(l!=r) down(rt);
	if(l==r) return l;
	int m=l+r>>1;
	if(seg[rt<<1]>=x) return query(x,l,m,rt<<1);
	return query(x-seg[rt<<1],m+1,r,rt<<1|1);
}

void build2(int l,int r,int rt,int *K)
{
	if(l==r)
		return seg[rt]=K[l-1],void();
	int m=l+r>>1;
	build2(l,m,rt<<1,K),build2(m+1,r,rt<<1|1,K);
	seg[rt]=max(seg[rt<<1],seg[rt<<1|1]);
}

int query2(int L,int R,int l,int r,int rt)
{
	if(L<=l&&R>=r)
		return seg[rt];
	int m=l+r>>1;
	if(R<=m) return query2(L,R,l,m,rt<<1);
	if(L>m) return query2(L,R,m+1,r,rt<<1|1);
	return max(query2(L,R,l,m,rt<<1),query2(L,R,m+1,r,rt<<1|1));
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
	int ans=-1,ansn=0;
	build(0,N,1);
	for(int i=0;i<C;++i)
	{
		int l=query(S[i]+1,0,N,1),r=query(E[i]+2,0,N,1);
		rel[i]=MP(l,r-1),modify(l+1,r-1,0,N,1);
	}
	build2(1,N,1,K);
	for(int i=0;i<C;++i)
	{
		int mx=query2(rel[i].F+1,rel[i].S,1,N,1);
		if(rel[i].F)
			oper[rel[i].F].pb(MP(max(mx,K[rel[i].F-1]),max(mx,R))),++cnt[max(mx,K[rel[i].F-1])];
		else
			oper[rel[i].F].pb(MP(N,max(mx,R))),++cnt[N];
		if(rel[i].S+1<N)
			oper[rel[i].S+1].pb(MP(max(mx,R),max(mx,K[rel[i].S])));
	}
	for(int i=0;i<N;++i)
	{
		for(auto j:oper[i])
			--cnt[j.F],++cnt[j.S];
		if(cnt[R]>ans)
			ans=cnt[R],ansn=i;
	}
	return ansn;
}

Compilation message

tournament.cpp: In function 'void build(int, int, int)':
tournament.cpp:24:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
tournament.cpp: In function 'void modify(int, int, int, int, int)':
tournament.cpp:41:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
tournament.cpp: In function 'int query(int, int, int, int)':
tournament.cpp:51:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
tournament.cpp: In function 'void build2(int, int, int, int*)':
tournament.cpp:60:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
tournament.cpp: In function 'int query2(int, int, int, int, int)':
tournament.cpp:69:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2688 KB Output is correct
2 Correct 9 ms 3200 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 8 ms 3200 KB Output is correct
5 Correct 29 ms 3072 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 8 ms 3200 KB Output is correct
8 Correct 9 ms 3200 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 8 ms 3200 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5796 KB Output is correct
2 Correct 100 ms 12160 KB Output is correct
3 Correct 23 ms 5636 KB Output is correct
4 Correct 96 ms 12152 KB Output is correct
5 Correct 95 ms 11896 KB Output is correct
6 Correct 82 ms 10032 KB Output is correct
7 Correct 97 ms 12152 KB Output is correct
8 Correct 103 ms 12152 KB Output is correct
9 Correct 18 ms 4736 KB Output is correct
10 Correct 26 ms 6420 KB Output is correct