oj.uz

Submission #414908

# Submission time Handle Problem Language Result Execution time Memory
414908 2021-05-31T10:33:57 Z cpp219 Jousting tournament (IOI12_tournament) C++14
100 / 100
 76 ms 3276 KB 
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 9;
const ll sz = (1 << 17);
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;

ll st[2*sz + 9],st2[2*sz + 9];

void Add(ll a,ll b){
    a += sz; st[a] = b;
    while(a != 1){
        a >>= 1;
        st[a] = max(st[a*2],st[a*2 + 1]);
    }
}

void Add2(ll a,ll b){
    a += sz;
    while(a){
        st2[a] += b; a >>= 1;
    }
}

ll GetMax(ll b,ll e){
    b += sz; e += sz;
    ll kq = 0;
    while(b <= e){
        kq = max(kq,st[b]); kq = max(kq,st[e]);
        b = (b + 1) >> 1; e = (e - 1) >> 1;
    }
    return kq;
}

ll Find(ll a){
    ll root = 1;
    while(root < sz){
        root *= 2;
        if (st2[root] < a){
            a -= st2[root]; root++;
        }
    }
    return root - sz;
}

ll nxt(ll a){
    a += sz;
    while(!st2[a]) a = (a + 1) >> 1;
    while(a < sz){
        a <<= 1;
        if (!st2[a]) a++;
    }
    return a - sz;
}

ll pre[N];

ll GetBestPosition(ll n,ll C,ll R,ll *K,ll *S,ll *E){
    for (ll i = 0;i < n - 1;i++) Add(i,K[i]);
    for (ll i = 0;i <= n;i++) Add2(i,1);
    for (ll i = 0;i < C;i++){
        ll b = Find(S[i] + 1),e = Find(E[i] + 2) - 1;
        if (GetMax(b,e - 1) < R) pre[b]++,pre[e + 1]--;
        while(1){
            //cout<<b<<" ";
            b = nxt(b + 1); //cout<<"?";
            if (b > e) break;
            Add2(b,-1);
        }
    }
    //exit(0);
    ll total = 0,mx = 0,chosen = 0;
    for (ll i = 0;i < n;i++){
        total += pre[i];
        if (total > mx){
            mx = total; chosen = i;
        }
    }
    return chosen;
}
/*
ll n,C,R,k[N],s[N],e[N];


int main(){
    //ios_base::sync_with_stdio(0);
    //cin.tie(0), cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>C>>R;
    for (ll i = 0;i < n - 1;i++) cin>>k[i];
    for (ll i = 0;i < C;i++) cin>>s[i]>>e[i];
    cout<<GetBestPosition(n,C,R,k,s,e);
}
*/

Compilation message

tournament.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
tournament.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      |

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 4 ms 532 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 4 ms 460 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1740 KB Output is correct
2 Correct 60 ms 3100 KB Output is correct
3 Correct 24 ms 2416 KB Output is correct
4 Correct 70 ms 3136 KB Output is correct
5 Correct 57 ms 3140 KB Output is correct
6 Correct 61 ms 3092 KB Output is correct
7 Correct 60 ms 3276 KB Output is correct
8 Correct 76 ms 3140 KB Output is correct
9 Correct 20 ms 2344 KB Output is correct
10 Correct 24 ms 3240 KB Output is correct