oj.uz

답안 #195128

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
195128 2020-01-16T06:48:10 Z sealnot123 마상시합 토너먼트 (IOI12_tournament) C++14
100 / 100
 164 ms 13936 KB 
//#include "grader.cpp"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;

const int N = 100005;
int p[N], fw[N], seg[N<<2], n, Rank, dp[N], L[N], R[N];
int* num;
set< pair<PII, int> > interval;
set< pair<PII, int> >::iterator it, it2;
vector<int> g[N];
int fin(int i){
	if(p[i]==i) return i;
	return p[i]=fin(p[i]);
}
void add(int a, int b){
	while(a<N) fw[a] += b, a+=(a&-a);
}
int get(int a){
	int b = 0;
	while(a) b += fw[a], a-=(a&-a);
	return b;
}
int bs(int a){
    int l=0, r=N-1;
    while(l<r){
        int m = (l+r)>>1;
        if(get(m)<a) l = m+1;
        else r = m;
    }
    return l;
}
void build(int l = 1, int r = n-1, int now = 1){
	if(l == r){ seg[now] = num[l-1]; return ;}
	int m = (l+r)>>1;
	build(l, m, now<<1); build(m+1, r, now<<1|1);
	seg[now] = max(seg[now<<1], seg[now<<1|1]);
}
int qu(int ll, int rr, int l = 1, int r = n-1, int now = 1){
	if(l > rr || r < ll) return -1;
	if(l >= ll && r <= rr) return seg[now];
	int m = (l+r)>>1;
	return max(qu(ll, rr, l, m, now<<1), qu(ll, rr, m+1, r, now<<1|1));
}
void dfs(int u, int v){
	int ch = (qu(L[u], R[u]-1)<Rank);
	//printf("==%d (%d,%d) %d\n",u,L[u],R[u],ch);
	if(ch) dp[u] = dp[v]+1;
	for(int e : g[u]){
        //printf("%d\n",e);
		dfs(e, u);
	}
}

int GetBestPosition(int n1, int c, int r, int *K, int *S, int *E) {
	// c is number of commands
	// r is rank of the late knight
	// K = rank of the knight in each positions (0 to n-1)
	// S and E are just 'l' and 'r'
	num = K;
	n = n1;
	Rank = r;
	int i,j,k,a,b,d;
	for(i=1;i<=n+1;i++) add(i, 1), p[i] = i;
	for(i=0;i<c;i++){
		int l = bs(S[i]+1);
		int r = bs(E[i]+1);
		L[i] = bs(S[i])+1;
		R[i] = r;
		it = interval.lower_bound({{L[i],0},0});
		while(it != interval.end() && it->x.x >= L[i] && it->x.y <= R[i]){
			it2 = it;
			it++;
			g[i].pb(it2->y);
			interval.erase(it2);
		}
		//printf("##%d\n==%d %d\n",i,L[i],R[i]);
		interval.insert({{L[i], R[i]},i});
		for(j = l; j < r; j=fin(j+1)){
			//printf("xx%d\n",j);
			add(j, -1);
			p[j] = fin(j+1);
//            if(get(j)-get(j-1)) add(j,-1);
		}
	}
	build();
	dfs(c-1, c);
	PII ans = (PII){0, 0};
	for(i=0;i<c;i++) if(g[i].empty()) ans = max((PII){dp[i], -L[i]+1}, ans);
  	return -ans.y;
}
/*
5 3 3
1 0 2 4
1 3
0 1
0 1

10 9 9
8 7 6 5 4 3 2 1 0
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1

10 3 5
0 4 7 2 9 1 3 6 8
3 7
1 3
0 3
*/

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:73:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,a,b,d;
          ^
tournament.cpp:73:12: warning: unused variable 'a' [-Wunused-variable]
  int i,j,k,a,b,d;
            ^
tournament.cpp:73:14: warning: unused variable 'b' [-Wunused-variable]
  int i,j,k,a,b,d;
              ^
tournament.cpp:73:16: warning: unused variable 'd' [-Wunused-variable]
  int i,j,k,a,b,d;
                ^

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2748 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 5 ms 2716 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 5 ms 2756 KB Output is correct
8 Correct 5 ms 2732 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 5 ms 2780 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 11 ms 3352 KB Output is correct
3 Correct 6 ms 2936 KB Output is correct
4 Correct 10 ms 3116 KB Output is correct
5 Correct 9 ms 3192 KB Output is correct
6 Correct 8 ms 3064 KB Output is correct
7 Correct 10 ms 3192 KB Output is correct
8 Correct 14 ms 3192 KB Output is correct
9 Correct 7 ms 2908 KB Output is correct
10 Correct 13 ms 3064 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 5892 KB Output is correct
2 Correct 140 ms 13936 KB Output is correct
3 Correct 39 ms 7260 KB Output is correct
4 Correct 136 ms 12316 KB Output is correct
5 Correct 132 ms 12644 KB Output is correct
6 Correct 164 ms 9040 KB Output is correct
7 Correct 136 ms 12892 KB Output is correct
8 Correct 137 ms 12852 KB Output is correct
9 Correct 26 ms 6752 KB Output is correct
10 Correct 37 ms 5860 KB Output is correct