oj.uz

Submission #851728

# Submission time Handle Problem Language Result Execution time Memory
851728 2023-09-20T13:26:59 Z abcvuitunggio Jousting tournament (IOI12_tournament) C++17
100 / 100
 99 ms 10592 KB 
#include <bits/stdc++.h>
using namespace std;
int n,st[400001][2],lazy[400001][2],l[100001],r[100001],f[100001];
vector <pair <int, int>> ve;
void down(int node, int l, int r, int i){
    if (!lazy[node][i]||l==r)
        return;
    st[node<<1][i]=st[node<<1|1][i]=0;
    lazy[node<<1][i]=lazy[node<<1|1][i]=1;
    lazy[node][i]=0;
}
void build(int node, int l, int r){
    st[node][0]=st[node][1]=r-l+1;
    if (l==r)
        return;
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
}
void update(int node, int l, int r, int u, int v, int i){
    if (l>v||r<u||l>r||u>v)
        return;
    if (l>=u&&r<=v){
        st[node][i]=0;
        lazy[node][i]=1;
        return;
    }
    down(node,l,r,i);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,i);
    update(node<<1|1,mid+1,r,u,v,i);
    st[node][i]=st[node<<1][i]+st[node<<1|1][i];
}
int get(int node, int l, int r, int val, int i){
    if (l==r)
        return l;
    down(node,l,r,i);
    int mid=(l+r)>>1;
    return (st[node<<1][i]<val?get(node<<1|1,mid+1,r,val-st[node<<1][i],i):get(node<<1,l,mid,val,i));
}
void update(int i, int val){
    i++;
    for (;i<=n;i+=i&(-i))
        f[i]+=val;
}
int get(int i){
    int res=0;
    i++;
    for (;i;i-=i&(-i))
        res+=f[i];
    return res;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
    n=N;
    build(1,0,N-1);
    for (int i=0;i<C;i++){
        S[i]=get(1,0,N-1,S[i]+1,0);
        E[i]=get(1,0,N-1,E[i]+1,1);
        update(1,0,N-1,S[i]+1,E[i],0);
        update(1,0,N-1,S[i],E[i]-1,1);
        ve.emplace_back(S[i],E[i]);
    }
    sort(ve.begin(),ve.end());
    l[0]=0;
    r[N-1]=N-1;
    for (int i=0;i<N-1;i++)
        l[i+1]=(K[i]>R?i+1:l[i]);
    for (int i=N-2;i>=0;i--)
        r[i]=(K[i]>R?i:r[i+1]);
    int x=0,y=0;
    pair <int, int> res={-1,-1};
    for (int i=0;i<N;i++){
        while (x<ve.size()&&ve[x].first<l[i]){
            update(ve[x].second,-1);
            x++;
        }
        while (y<ve.size()&&ve[y].first<=i){
            update(ve[y].second,1);
            y++;
        }
        res=max(res,{get(r[i])-get(i-1),-i});
    }
    return -res.second;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while (x<ve.size()&&ve[x].first<l[i]){
      |                ~^~~~~~~~~~
tournament.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         while (y<ve.size()&&ve[y].first<=i){
      |                ~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2504 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 4 ms 2908 KB Output is correct
3 Correct 1 ms 2508 KB Output is correct
4 Correct 4 ms 3160 KB Output is correct
5 Correct 5 ms 2904 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct
7 Correct 5 ms 2908 KB Output is correct
8 Correct 5 ms 2908 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 5 ms 2904 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4816 KB Output is correct
2 Correct 96 ms 10180 KB Output is correct
3 Correct 16 ms 7024 KB Output is correct
4 Correct 91 ms 10592 KB Output is correct
5 Correct 92 ms 9924 KB Output is correct
6 Correct 70 ms 9416 KB Output is correct
7 Correct 93 ms 10088 KB Output is correct
8 Correct 99 ms 10088 KB Output is correct
9 Correct 12 ms 6488 KB Output is correct
10 Correct 18 ms 7768 KB Output is correct