Submission #1111833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111833		malacia	Jousting tournament (IOI12_tournament)	C++17	0 / 100	248 ms	262144 KiB

tournament

#include<bits/stdc++.h>
#define fo(i,x,n) for(int i=x;i<=n;++i)
#define fi(i,x,n) for(int i=x;i>=n;--i)
#define SYNCHRONIZE ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long 
#define ld long double
#define pii pair<int,int> 
#define pil pair<int,ll>
#define BIT(i,mask) ((mask >> (i-1)) & 1) 
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define maxn 100005
#define uni(vt) vt.resize(unique(vt.begin(),vt.end()) - vt.begin());
#define DAOBIT(i,mask) ((mask ^ (1ll<<i-1))) 
#define OFFBIT(i,mask) ((mask & ~(1ll << (i - 1))))
#define ONBIT(i,mask) ((mask | (1ll << (i - 1)))) 
using namespace std;
//----------------- STRUCTURE ---------------
 
//----------------- DECLARE ------------------
int n, c , r , k[maxn];
int bit[maxn], Max[maxn][19] , st[4*maxn][2] ;
bool lz[maxn][2];
//----------------- FUNCTION -----------------
void prepare() {
    
    fi(i,n,1) {
        Max[i][0] = k[i];
 
        for(int j = 1 ; i + (1<<j) - 1 <= n ; ++j) 
            Max[i][j] = max(Max[i][j-1] , Max[i+(1<<j-1)][j-1]);
    }
}
 
int getMaxPoint(int l ,int r) {
    int lg = __lg(r-l+1);
    return max(Max[l][lg] , Max[r-(1<<lg)+1][lg]);
}
 
void update(int pos , int val)
{
    for(;pos <= n ; pos += pos&(-pos) )
          bit[pos] += val;
}
 
int getPoint(int pos)
{ 
    int res = 0;
    for(;pos >0 ; pos -= pos&(-pos)) 
                res += bit[pos];
    return res ;
}
 
void built(int id , int l , int r) {
    if(l == r) {
        st[id][0] =  st[id][1] = 1;
        lz[id][0] = lz[id][0] = 1;
        return;
    }
    int mid = (l+r)>>1;
    built(id<<1,l,mid);
    built(id<<1|1,mid+1,r);
    lz[id][0] = lz[id][1] = 1;
    st[id][0] = st[id<<1][0]  + st[id<<1|1][0];
    st[id][1] = st[id<<1][1] + st[id<<1|1][1];
}
 
 
void DOWN(int id , int type ) {
    st[id<<1][type] = 0;
    lz[id<<1][type] = 0;
 
 
    st[id<<1|1][type] =0;
    lz[id<<1|1][type] = 0 ;
}
 
int get(int pos , int type) {
    int id = 1, l = 1 , r = n ,mid;
 
    while(l < r) {
        mid = (l+r)>>1;
        if(lz[id] == 0) DOWN(id,type);
 
        if(pos <= st[id<<1][type]) {
            r = mid;
            id <<= 1;
        }
        else {
            pos -= st[id<<1][type];
            l = mid+1;
            id = (id<<1|1);
        }
    }
    return l;
}
 
void update(int id , int l , int r , int u , int v, int type) {
    if(u <= l && r <= v) {
        st[id][type] = 0;
        lz[id][type] = 0;
        return ;
    }
 
    if(lz[id] == 0) DOWN(id,type);
    int mid = (l+r)>>1;
    if(u <= mid) {
        update(id<<1,l,mid,u,v,type);
        if(v > mid) update(id<<1|1,mid+1,r,u,v,type);
    }
    else update(id<<1|1,mid+1,r,u,v,type);
    st[id][type] = st[id<<1][type] + st[id<<1|1][type];
}
 
int GetBestPosition(int N, int C, int R, int K[], int S[], int E[]) {
    n = N ,c= C,r = R;
    fo(i,1,n-1) k[i] = K[i-1];
    built(1,1,n);
  	prepare();
 
    fo(i,1,c) {
        int u = S[i-1],v = E[i-1];
        int s = get(u,0) , e = get(v,1);
        update(1,1,n,s+1,e,0);
        update(1,1,n,s,e-1,1);
 
        if(getMaxPoint(s,e-1) < r){
            update(s,1);
            update(e,-1);
        }
    }
 
    int mxPoint = 0 , temp = -1;
 
    fo(i,1,n) if(getPoint(i) > mxPoint) {
        mxPoint = getPoint(i);
        temp= i;
    }
 
    return  temp;
}
//----------------- MAIN PRO ------------------

Compilation message (stderr)

tournament.cpp: In function 'void prepare()':
tournament.cpp:31:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   31 |             Max[i][j] = max(Max[i][j-1] , Max[i+(1<<j-1)][j-1]);
      |                                                     ~^~
tournament.cpp: In function 'void built(int, int, int)':
tournament.cpp:57:19: warning: operation on 'lz[id][0]' may be undefined [-Wsequence-point]
   57 |         lz[id][0] = lz[id][0] = 1;
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~

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