Submission #709677

#	Time	Username	Problem	Language	Result	Execution time	Memory
709677		Pherokung	Jousting tournament (IOI12_tournament)	C++14	0 / 100	171 ms	5880 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF 1000000007
#define F first
#define S second

int n,c,v,a[MAXN],s,e,mid,x,l,r,arr[MAXN];
typedef pair<int,int> paa;

struct node{
    int val,lazy,mx;
    node *l, *r;
};
node top;

void build(node *pos,int be,int ed){
    if(be == ed){
        pos->val = 1;
        pos->lazy = 0;
        pos->mx = a[be];
        return;
    }
    pos->l = new node, pos->r = new node;
    int mid = (be + ed) / 2;
    build(pos->l,be,mid), build(pos->r,mid+1,ed);
    pos->lazy = 0;
    pos->val = pos->l->val + pos->r->val;
    pos->mx = max(pos->l->mx,pos->r->mx);
}

void update(node *pos,int be,int ed,int x,int y){
    if(pos->lazy){
        pos->lazy = 0;
        pos->val = 0;
        pos->mx = -INF;
        if(be != ed) pos->l->lazy = 1, pos->r->lazy = 1;
    }

    if(be > ed || y < be || ed < x) return;
    if(x <= be && ed <= y){
        pos->val = 0;
        pos->mx = -INF;
        if(be != ed) pos->l->lazy = 1, pos->r->lazy = 1;
        return;
    }
    int mid = (be+ed)/2;
    update(pos->l,be,mid,x,y), update(pos->r,mid+1,ed,x,y);
    pos->val = pos->l->val + pos->r->val;
    pos->mx = max(pos->l->mx,pos->r->mx);
}

paa query(node *pos,int be,int ed,int x,int y){
    if(pos->lazy){
        pos->lazy = 0;
        pos->val = 0;
        pos->mx = -INF;
        if(be != ed) pos->l->lazy = 1, pos->r->lazy = 1;
    }
    if(be > ed || y < be || ed < x) return {0,-INF};
    if(x <= be && ed <= y) return {pos->val,pos->mx};
    int mid = (be+ed)/2;
    paa L = query(pos->l,be,mid,x,y), R = query(pos->r,mid+1,ed,x,y);
    return {L.F+R.F,max(L.S,R.S)};
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N,c = C, v = R+1;
    for(int i=1;i<=n-1;i++) a[i] = K[i-1] + 1;
    a[n] = 0;
    build(&top,1,n);
    for(int i=1;i<=c;i++){
        S[i-1]++, E[i-1]++;
        //printf("??%d %d\n",S[i-1],E[i-1]);
        x = S[i-1];
        s = 1, e = n;
        if(x == 1){
            l = 1;
        }
        else{
            while(s <= e){
                mid = (s+e)/2;
                //printf("!!!!! (%d %d) %d %d \n",s,e,mid,query(&top,1,n,1,mid).F);
                if(query(&top,1,n,1,mid).F < x){
                    s = mid+1;
                }
                else e = mid-1;
            }
            l = s;
        }

        x = E[i-1];
        s = 1, e = n;
        while(s <= e){
            mid = (s+e)/2;
            if(query(&top,1,n,1,mid).F <= x){
                s = mid+1;
            }
            else e = mid-1;
        }
        r = e;

        int val_r = a[r], val_l = query(&top,1,n,l,r-1).S;
        //printf("!! %d %d : %d %d\n",l,r,val_l,val_r);
        if(val_l < v){
            arr[l]++, arr[r+1]--;
        }
        if(l < r) update(&top,1,n,l,r-1);

    }

    int sum = 0, ans, mxx=-INF;
    for(int i=1;i<=n+1;i++){
        sum += arr[i];
        if(sum > mxx){
            mxx = sum;
            ans = i-1;
        }
    }

    return ans;

}

/*
6 5 5
0 1 2 3 4
0 1
0 1
0 1
0 1
0 1

6 5 5
0 1 2 3 4
0 1
0 1
0 1
0 1
0 1

6 5 5
0 1 2 3 4
4 5
3 4
2 3
1 2
0 1
*/

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:103:13: warning: unused variable 'val_r' [-Wunused-variable]
  103 |         int val_r = a[r], val_l = query(&top,1,n,l,r-1).S;
      |             ^~~~~
tournament.cpp:121:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |     return ans;
      |            ^~~

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