oj.uz

Submission #586938

# Submission time Handle Problem Language Result Execution time Memory
586938 2022-07-01T05:47:55 Z krit3379 Jousting tournament (IOI12_tournament) C++17
100 / 100
 281 ms 13688 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using namespace __gnu_pbds;
using pii = pair<int,int>;
using piii = pair<int,pair<int,int>>;
#define N 100005

tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> s;
tree<piii,null_type,less<piii>,rb_tree_tag,tree_order_statistics_node_update> q;
pair<int,int> seg[N];
int dp[N],ma=-1,ans;
vector<int> op[N];

int val(int l,int r){
    if(l>r)return 0;
    if(l)return dp[r]-dp[l-1];
    return dp[r];
}

int ch(int l,int r,int m){
    return val(l,m-1)+val(m,r-1);
}

int GetBestPosition(int n,int c,int R,int *K,int *S,int *E) {
    int i,l,r,mid;
    for(i=0;i<n;i++)s.insert({i,i});
    for(i=0;i<c;i++){
        auto l=s.find_by_order(S[i]),r=s.find_by_order(E[i]);
        seg[i]={(*l).first,(*r).second};
        r++;
        while(l!=r)s.erase(l++);
        s.insert(seg[i]);
        op[seg[i].first].push_back(i+1);
        op[seg[i].second+1].push_back(-i-1);
    }
    for(i=0;i<n-1;i++){
        if(i)dp[i]+=dp[i-1];
        dp[i]+=K[i]>R;
    }
    for(i=0;i<n;i++){
        for(auto id:op[i]){
            if(id>0)q.insert({id-1,seg[id-1]});
            else q.erase({-id-1,seg[-id-1]});
        }
        l=0,r=((int)q.size())-1;
        while(l<=r){
            mid=(l+r)/2;
            auto it=q.find_by_order(mid);
            if(!ch((*it).second.first,(*it).second.second,i)){
                if(mid>ma)ma=mid,ans=i;
                l=mid+1;
            }
            else r=mid-1;
        }
    }
    return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 3 ms 2656 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 10 ms 3156 KB Output is correct
3 Correct 4 ms 2900 KB Output is correct
4 Correct 9 ms 3156 KB Output is correct
5 Correct 9 ms 3156 KB Output is correct
6 Correct 6 ms 3156 KB Output is correct
7 Correct 12 ms 3156 KB Output is correct
8 Correct 11 ms 3156 KB Output is correct
9 Correct 4 ms 2900 KB Output is correct
10 Correct 9 ms 3160 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 6660 KB Output is correct
2 Correct 281 ms 13688 KB Output is correct
3 Correct 89 ms 9968 KB Output is correct
4 Correct 243 ms 11208 KB Output is correct
5 Correct 244 ms 11288 KB Output is correct
6 Correct 160 ms 10572 KB Output is correct
7 Correct 253 ms 11508 KB Output is correct
8 Correct 253 ms 11324 KB Output is correct
9 Correct 79 ms 9684 KB Output is correct
10 Correct 89 ms 9772 KB Output is correct