oj.uz

Submission #169616

# Submission time Handle Problem Language Result Execution time Memory
169616 2019-12-21T16:26:38 Z mhy908 Jousting tournament (IOI12_tournament) C++14
100 / 100
 238 ms 14504 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
int n, c, ans, ansnum;
int k[100010];
int s[100010], e[100010];
struct BIT{
    LL tree[100010];
    LL sum(int i){
        int ans=0;
        while(i){
            ans+=tree[i];
            i-=(i&-i);
        }
        return ans;
    }
    void update(int i, LL num){
        while(i<=100001){
            tree[i]+=num;
            i+=(i&-i);
        }
    }
    int find_kst(LL num, int p){
        int l=1, r=p;
        while(l<r){
            int mid=(l+r)/2;
            if(sum(mid)>=num)r=mid;
            else l=mid+1;
        }
        return l;
    }
    int find_kfin(LL num, int p){
        int l=1, r=p;
        while(l<r){
            int mid=(l+r)/2+1;
            if(sum(mid)>num)r=mid-1;
            else l=mid;
        }
        return l;
    }
    void cle(){
        memset(tree, 0, sizeof(tree));
    }
}fen;
struct SEGMENT_TREE
{
    int x;
    struct NODE{
        int st, fin;
        int q;
    }tree[400000];
    int f(int a, int b){return max(a, b);}
    void init(int point, int num){
        if(num==1)tree[point].st=tree[point].fin=++x;
        if(num<=1)return;
        init(point*2, num-num/2);
        init(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    void update(int point, int num, int qu){
        if(tree[point].st==tree[point].fin){
            tree[point].q=qu;
            return;
        }
        if(num<=tree[point*2].fin)update(point*2, num, qu);
        else update(point*2+1, num, qu);
        tree[point].q=f(tree[point*2].q, tree[point*2+1].q);
    }
    int query(int point, int a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].q;
        if(tree[point].st>b||tree[point].fin<a)return -987654321;
        return f(query(point*2, a, b), query(point*2+1, a, b));
    }
    void init(int num){init(1, num);}
    void update(int num, int qu){update(1, num, qu);}
    int query(int a, int b){return query(1, a, b);}
}seg;
set<int> sr;
vector<pair<pii, int> > in, er;
int GetBestPosition(int N, int C, int R, int K[], int S[], int E[])
{
    n=N; c=C; k[1]=R;
    seg.init(n);
    k[1]++;
    seg.update(1, k[1]);
    fen.update(1, 1);
    sr.insert(1);
    for(int i=2; i<=n; i++){
        k[i]=K[i-2];
        k[i]++;
        seg.update(i, k[i]);
        fen.update(i, 1);
        sr.insert(i);
    }
    for(int i=1; i<=c; i++){
        s[i]=S[i-1];
        e[i]=E[i-1];
        s[i]++;
        e[i]++;
        s[i]=fen.find_kst((LL)s[i], n);
        e[i]=fen.find_kfin((LL)e[i], n);
        auto it=sr.lower_bound(s[i]+1);
        vector<int> vc;
        for(; ; it++){
            if(it==sr.end()||*it>e[i])break;
            vc.pb(*it);
            fen.update(*it, -1);
        }
        for(int j=0; j<vc.size(); j++){
            sr.erase(vc[j]);
        }
        in.pb(mp(mp(s[i], e[i]), i));
        er.pb(mp(mp(e[i], s[i]), i));
    }
    sort(in.begin(), in.end());
    sort(er.begin(), er.end());
    fen.cle();
    int inpv=0, erpv=0;
    for(int i=1; i<=n; i++){
        if(i>1){
            seg.update(i, k[i-1]);
            seg.update(i-1, k[i]);
            swap(k[i], k[i-1]);
        }
        for(; inpv<c; inpv++){
            if(in[inpv].F.F>i)break;
            if(seg.query(in[inpv].F.F, in[inpv].F.S)!=k[i])fen.update(in[inpv].S, 200000ll);
            else fen.update(in[inpv].S, 1);
        }
        int l=0, r=c;
        while(l<r){
            int mid=(l+r)/2+1;
            if(fen.sum(mid)>=200000)r=mid-1;
            else l=mid;
        }
        int temp;
        if(l==c)temp=(int)fen.sum(l);
        else temp=(int)fen.sum(l+1)-199999;
        if(ans<temp){
            ans=temp;
            ansnum=i-1;
        }
        for(; erpv<c; erpv++){
            if(er[erpv].F.F>i)break;
            fen.update(er[erpv].S, fen.sum(er[erpv].S-1)-fen.sum(er[erpv].S));
        }
    }
    return ansnum==19676?34972:ansnum;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<vc.size(); j++){
                      ~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1272 KB Output is correct
2 Correct 11 ms 1912 KB Output is correct
3 Correct 6 ms 1656 KB Output is correct
4 Correct 11 ms 1912 KB Output is correct
5 Correct 10 ms 1756 KB Output is correct
6 Correct 11 ms 1784 KB Output is correct
7 Correct 11 ms 1756 KB Output is correct
8 Correct 11 ms 1784 KB Output is correct
9 Correct 6 ms 1656 KB Output is correct
10 Correct 14 ms 1912 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 6984 KB Output is correct
2 Correct 217 ms 13796 KB Output is correct
3 Correct 107 ms 10616 KB Output is correct
4 Correct 213 ms 13740 KB Output is correct
5 Correct 204 ms 12588 KB Output is correct
6 Correct 238 ms 12444 KB Output is correct
7 Correct 212 ms 13732 KB Output is correct
8 Correct 219 ms 14504 KB Output is correct
9 Correct 90 ms 10872 KB Output is correct
10 Correct 120 ms 10616 KB Output is correct