oj.uz

Submission #945726

# Submission time Handle Problem Language Result Execution time Memory
945726 2024-03-14T06:46:46 Z beepbeepsheep Jousting tournament (IOI12_tournament) C++17
100 / 100
 284 ms 31176 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>

const ll inf=1e15;
const ll maxn=1e5+5;
const ll mod=1e9+7;
vector<ii> v;
stack<ii> s; //ending point, value

struct node2{
    ll s,e,m,val,flag;
    node2 *l,*r;
    node2 (ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1,val=e-s+1,flag=0;
        if (s!=e) l=new node2(s,m),r=new node2(m+1,e);
    }
    void prop(){
        if (!flag) return;
        val=0;
        if (s==e){
            flag=0;
            return;
        }
        l->flag=flag;
        r->flag=flag;
        flag=0;
    }
    void upd(ll x, ll y){
        if (x<=s && e<=y){
            flag=1;
            return;
        }
        if (x>m) r->upd(x,y);
        else if (y<=m) l->upd(x,y);
        else l->upd(x,y),r->upd(x,y);
        l->prop(),r->prop();
        val=l->val+r->val;
    }
    ll query(ll x, ll y){
        prop();
        if (x<=s && e<=y) return val;
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return l->query(x,y)+r->query(x,y);
    }
}*root2;
struct node{
    ll s,e,m;
    ll val;
    node *l,*r;
    node (ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1,val=0;
        if (s!=e) l=new node(s,m),r=new node(m+1,e);
    }
    void upd(ll x, ll v){
        if (s==e){
            val=v;
            return;
        }
        if (x>m) r->upd(x,v);
        else l->upd(x,v);
        val=max(l->val,r->val);
    }
    ll query(ll x, ll y){
        if (x<=s && e<=y) return val;
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return max(l->query(x,y),r->query(x,y));
    }
}*root;
ll n;
ll bsta(ll x, ll t){
    if (t==1){
        ll l=0,r=n,m;
        while (l!=r-1){
            m=(l+r)>>1;
            ll res=root2->query(1,m);
            if (res>=x) r=m;
            else l=m;
        }
        return r;
    } else{
        ll l=1,r=n+1,m;
        while (l!=r-1){
            m=(l+r)>>1;
            ll res=root2->query(1,m);
            if (res<=x) l=m;
            else r=m;
        }
        return l;
    }
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=N;
    root2=new node2(1,N);
    for (int i=0;i<C;i++){
        S[i]++,E[i]++;
        S[i]=bsta(S[i],1);
        E[i]=bsta(E[i],0);
        root2->upd(S[i]+1,E[i]);
        v.emplace_back(S[i],-E[i]);
        //cerr<<S[i]<<' '<<E[i]<<endl;
    }
    root=new node(1,N);
    for (int i=1;i<N;i++) root->upd(i,K[i-1]);
    ll ans=-1,pos=-1;
    sort(v.begin(),v.end());
    s.emplace(inf,0);
    for (auto [l,r]:v){
        r=-r;
        while (s.size() && l>s.top().first) s.pop();
        ll res=root->query(l,r-1);
        //cerr<<l<<' '<<r<<' '<<res<<endl;
        if (res>R){
            s.emplace(r,0);
        }
        else{
            ll endTime,val;
            tie(endTime,val)=s.top();
            s.emplace(r,val+1);
        }
        if (s.top().second>ans){
            ans=s.top().second;
            pos=l;
        }
    }
    return pos-1;

}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 8 ms 1728 KB Output is correct
3 Correct 3 ms 1628 KB Output is correct
4 Correct 8 ms 1884 KB Output is correct
5 Correct 8 ms 1628 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 8 ms 1884 KB Output is correct
8 Correct 8 ms 1920 KB Output is correct
9 Correct 2 ms 1628 KB Output is correct
10 Correct 12 ms 1880 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 13964 KB Output is correct
2 Correct 256 ms 31176 KB Output is correct
3 Correct 49 ms 26652 KB Output is correct
4 Correct 252 ms 30156 KB Output is correct
5 Correct 284 ms 29456 KB Output is correct
6 Correct 234 ms 28364 KB Output is correct
7 Correct 262 ms 30644 KB Output is correct
8 Correct 269 ms 30412 KB Output is correct
9 Correct 32 ms 26460 KB Output is correct
10 Correct 53 ms 26504 KB Output is correct