Submission #684154

#	Time	Username	Problem	Language	Result	Execution time	Memory
684154		Khizri	Jousting tournament (IOI12_tournament)	C++17	17 / 100	461 ms	2164 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=1e5+5;
int n,q,k;
vector<int>arr;
vector<pii>p,vt,p2;
int tree[4*mxn];
void build(int node,int l,int r){
    if(l==r){
        tree[node]=arr[l];
        return;
    }
    int m=(l+r)/2;
    build(2*node,l,m);
    build(2*node+1,m+1,r);
    tree[node]=max(tree[2*node],tree[2*node+1]);
}
int query(int node,int l,int r,int ql,int qr){
    if(r<ql||l>qr) return -1;
    if(ql<=l&&r<=qr) return tree[node];
    int m=(l+r)/2;
    int x=query(2*node,l,m,ql,qr);
    int y=query(2*node+1,m+1,r,ql,qr);
    return max(x,y);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;
    q=C;
    k=R;
    for(int i=0;i<n-1;i++){
        arr.pb(K[i]);
    }
    for(int i=0;i<q;i++){
        p.pb({S[i],E[i]});
    }
    for(int i=0;i<n;i++){
        vt.pb({i,i});
    }
    for(int i=0;i<q;i++){
        int l=p[i].F,r=p[i].S;
        int a=1e9,b=-1e9;
        for(int j=l;j<=r;j++){
            a=min(a,vt[j].F);
            b=max(b,vt[j].S);
        }
        p2.pb({a,b});
        int say=r-l;
        while(say--){
            vt.erase(vt.begin()+l);
        }
        vt[l]={a,b};
    }
    if(n>1000) return 0;
    build(1,0,n-2);
    int ans=0,pl=0;
    for(int i=0;i<n;i++){
        int cnt=0;
        for(auto [l,r]:p2){
            if(i>=l&&i<=r){
                int l1=l,r1=i-1;
                int l2=i+1,r2=r;
                int cur=-1;
                if(r1>=l1){
                    cur=max(cur,query(1,0,n-2,l1,r1));
                }
                if(r2>=l2){
                    cur=max(cur,query(1,0,n-2,l2-1,r2-1));
                }
                if(k>cur){
                    cnt++;
                }
            }
        }
        if(cnt>ans){
            ans=cnt;
            pl=i;
        }
    }
    return pl;
}
/*
17 5 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3 5
5 8
8 10
3 5
3 6
*/

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