oj.uz

Submission #422673

# Submission time Handle Problem Language Result Execution time Memory
422673 2021-06-10T10:00:56 Z Bill_00 Jousting tournament (IOI12_tournament) C++14
100 / 100
 206 ms 16536 KB 
#include <bits/stdc++.h>
using namespace std;
int lazy[2000000],node[1000000],mx[1000000],another[1000000],lazyanother[1000000];
void update(int id,int l,int r,int L,int R,int x){
	if(lazy[id]!=-1){
		node[id]=(lazy[id]*(r-l+1));
		lazy[id*2]=lazy[id];
		lazy[id*2+1]=lazy[id];
		lazy[id]=-1;
	}
	if(r<L || R<l) return;
	if(L<=l && r<=R){
		node[id]=(x*(r-l+1));
		lazy[id*2]=x;
		lazy[id*2+1]=x;
		return;
	}
	int m=l+r>>1;
	update(id*2,l,m,L,R,x);
	update(id*2+1,m+1,r,L,R,x);
	node[id]=node[id*2]+node[id*2+1];
}
int query(int id,int l,int r,int x){
	if(lazy[id]!=-1){
		node[id]=(lazy[id]*(r-l+1));
		int m=l+r>>1;
		node[id*2]=lazy[id]*(m-l+1);
		node[id*2+1]=lazy[id]*(r-m);
		lazy[id*4]=lazy[id];
		lazy[id*4+1]=lazy[id];
		lazy[id*4+2]=lazy[id];
		lazy[id*4+3]=lazy[id];
		lazy[id]=-1;
	}
	if(l==r) return l;
	int m=l+r>>1;
	if(node[id*2]>=x) return query(id*2,l,m,x);
	else return query(id*2+1,m+1,r,x-node[id*2]);
}
int rightt[100005];
void build(int id,int l,int r,int pos,int x){
	if(l==r){
		mx[id]=x;
		return;
	}
	int m=l+r>>1;
	if(m>=pos) build(id*2,l,m,pos,x);
	else build(id*2+1,m+1,r,pos,x);
	mx[id]=max(mx[id*2],mx[id*2+1]);
}
int query1(int id,int l,int r,int L,int R){
	if(r<L || R<l) return 0;
	if(L<=l && r<=R) return mx[id];
	int m=l+r>>1;
	return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
void update1(int id,int l,int r,int L,int R){
	another[id]+=(lazyanother[id]*(r-l+1));
	lazyanother[id*2]+=lazyanother[id];
	lazyanother[id*2+1]+=lazyanother[id];
	lazyanother[id]=0;
	if(r<L || R<l) return;
	if(L<=l && r<=R){
		another[id]+=(r-l+1);
		lazyanother[id*2]++;
		lazyanother[id*2+1]++;
		return;
	}
	int m=l+r>>1;
	update1(id*2,l,m,L,R);
	update1(id*2+1,m+1,r,L,R);
	another[id]=another[id*2]+another[id*2+1];
}
int query2(int id,int l,int r,int pos){
	another[id]+=(lazyanother[id]*(r-l+1));
	lazyanother[id*2]+=lazyanother[id];
	lazyanother[id*2+1]+=lazyanother[id];
	lazyanother[id]=0;
	if(l==r) return another[id];
	int m=l+r>>1;
	if(m>=pos) return query2(id*2,l,m,pos);
	else return query2(id*2+1,m+1,r,pos);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	memset(lazy,-1,sizeof(lazy));
	for(int i=0;i<N;i++){
		update(1,0,N-1,i,i,1);
		rightt[i]=i;
	}
	for(int i=0;i<(N-1);i++){
		build(1,0,N-1,i,K[i]);
	}
	// cout << node[1] << '\n';
	for(int i=0;i<C;i++){
		int x=query(1,0,N-1,S[i]+1);
		int y=query(1,0,N-1,E[i]+1);
		// cout << x << ' ' << y << '\n';
		update(1,0,N-1,x+1,y,0);
		rightt[x]=rightt[y];
		// cout << x << ' ' << rightt[x] << '\n';
		int lol=query1(1,0,N-1,x,rightt[y]-1);
		// cout << lol << '\n';
		if(R>lol) update1(1,0,N-1,x,rightt[x]);
	}
	pair<int,int>answer={0,-1000000000};
	for(int i=0;i<N;i++){
		answer=max(answer,{query2(1,0,N-1,i),-i});
	}
	return -answer.second;
}

Compilation message

tournament.cpp: In function 'void update(int, int, int, int, int, int)':
tournament.cpp:18:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |  int m=l+r>>1;
      |        ~^~
tournament.cpp: In function 'int query(int, int, int, int)':
tournament.cpp:26:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int m=l+r>>1;
      |         ~^~
tournament.cpp:36:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |  int m=l+r>>1;
      |        ~^~
tournament.cpp: In function 'void build(int, int, int, int, int)':
tournament.cpp:46:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int m=l+r>>1;
      |        ~^~
tournament.cpp: In function 'int query1(int, int, int, int, int)':
tournament.cpp:54:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |  int m=l+r>>1;
      |        ~^~
tournament.cpp: In function 'void update1(int, int, int, int, int)':
tournament.cpp:69:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |  int m=l+r>>1;
      |        ~^~
tournament.cpp: In function 'int query2(int, int, int, int)':
tournament.cpp:80:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |  int m=l+r>>1;
      |        ~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 11 ms 8524 KB Output is correct
3 Correct 7 ms 8524 KB Output is correct
4 Correct 11 ms 8600 KB Output is correct
5 Correct 10 ms 8584 KB Output is correct
6 Correct 12 ms 8524 KB Output is correct
7 Correct 14 ms 8572 KB Output is correct
8 Correct 14 ms 8508 KB Output is correct
9 Correct 7 ms 8524 KB Output is correct
10 Correct 12 ms 8572 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 11956 KB Output is correct
2 Correct 192 ms 16384 KB Output is correct
3 Correct 74 ms 14644 KB Output is correct
4 Correct 184 ms 16536 KB Output is correct
5 Correct 206 ms 16352 KB Output is correct
6 Correct 168 ms 15744 KB Output is correct
7 Correct 200 ms 16416 KB Output is correct
8 Correct 184 ms 16452 KB Output is correct
9 Correct 65 ms 14600 KB Output is correct
10 Correct 74 ms 14636 KB Output is correct