Submission #1159799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159799		salmon	Specijacija (COCI20_specijacija)	C++20	110 / 110	1492 ms	151888 KiB

Main

#include <bits/stdc++.h>
using namespace std;

long long N;
int Q;
int t;
vector<int> st;
vector<int> l;
vector<int> r;
int root[200100];
vector<int> children[400100];
int cont = 0;
int cont1 = 1;
int na[400100];
pair<int,int> rang[400100];
long long ans[400100];
int parent[400100][30];
int d[400100];
map<pair<int,int>,int> mep;

void build(int s, int e){
    st.push_back(1);
    int in = cont;
    l.push_back(0);
    r.push_back(0);
    cont++;

    int m = (s + e)/2;

    if(s != e){
        l[in] = cont;
        build(s,m);
        r[in] = cont;
        build(m+1,e);

        st[in] = st[r[in]] + st[l[in]];
    }
}

void update(int c, int i, int s, int e){
    st.push_back(st[c] - 1);
    l.push_back(l[c]);
    r.push_back(r[c]);
    int in = cont;

    cont++;

    int m = (s + e)/2;

    if(s != e){
        if(i <= m){
            l[in] = cont;
            update(l[c],i,s,m);
        }
        else{
            r[in] = cont;
            update(r[c],i,m+1,e);
        }
    }
}

int query(int i, int v, int s, int e){
    if(s == e) return s;

    int m = (s + e)/2;

    if(st[l[i]] < v){
        v -= st[l[i]];
        return query(r[i],v,m + 1,e);
    }
    else{
        return query(l[i],v,s,m);
    }
}

void dfs(int i, int de){
    d[i] = de;

    for(int j : children[i]) dfs(j,de + 1);
}

int main(){

    scanf(" %lld",&N);
    scanf(" %d",&Q);
    scanf(" %d",&t);

    root[0] = 0;

    vector<long long> v;

    for(long long int i = 1; i <= N; i++){
        long long int h;
        scanf(" %lld\n",&h);
        v.push_back(h - (i * (i - 1))/2 );
    }

    for(int i = 1; i <= N + 1; i++){
        na[i] = i;
        mep[{i,i}] = i;
        rang[i] = {i,i};
    }

    for(int i = 1; i <= N * 2 + 5; i++){
        parent[i][0] = -1;
    }

    build(1,N+2);

    cont1 = N + 2;

    for(int i = 1; i <= N; i++){
        int va = v.back();
        v.pop_back();

        int it1 = query(root[i - 1],va,1,N+2);
        int it2 = query(root[i - 1],va + 1,1,N+2);
        int it3 = query(root[i - 1],va + 2,1,N+2);

        children[cont1].push_back(na[it1]);
        children[cont1].push_back(na[it2]);
        parent[na[it2]][0] = cont1;
        parent[na[it1]][0] = cont1;
        na[it1] = cont1;
        mep[{it1,it3-1}] = cont1;
        rang[cont1] = {it1,it3-1};
        ans[cont1] = va + (N + 1 - i) * (N - i) / 2;
        cont1++;

        root[i] = cont;
        update(root[i - 1],it2,1,N+2);
    }
   /*printf("\n");

    for(int i = 1; i <= N * 2; i++){
        printf("%d ",parent[i][0]);
    }
    printf("\n");*/


    dfs(cont1 - 1,0);

    /*for(int i = 1; i <= N * 2; i++){
        printf("%d ",d[i]);
    }
    printf("\n");*/

    for(int j = 1; j < 30; j++){
        for(int i = 0; i < N * 2 + 5; i++){
            if(parent[i][j - 1] != -1){
                parent[i][j] = parent[parent[i][j - 1]  ][j - 1];
            }
        }
    }

    long long z = 0;
    for(int i = 0; i < Q; i++){
        long long h;
        scanf(" %lld",&h);

        h = (h - 1 + t * z) % ((N + 1) * (N + 2) / 2  ) + 1;

        int s = 1;
        int e = N + 1;
        while(s != e){
            long long m = (s + e + 1)/2;

            if( (m )* (m - 1)/2 < h){
                s = m;
            }
            else{
                e = m - 1;
            }
        }

        h -= (s * (long long) (s - 1)) /2;
        int l = s;

        //blak

        long long h1;

        scanf(" %lld",&h1);

        h1 = (h1 - 1 + t * z) % ((N + 1) * (N + 2) / 2  ) + 1;

        s = 1;
        e = N + 1;
        while(s != e){
            long long m = (s + e + 1)/2;

            if( (m )* (m - 1)/2 < h1){
                s = m;
            }
            else{
                e = m - 1;
            }
        }

        h1 -= (s * (long long) (s - 1)) /2;
        int l1 = s;
//printf("%d %d\n",h,h1);
        assert (h <= N + 1 && 1 <= h);
        assert (h1 <= N + 1 && 1 <= h1);

        int it1 = query(root[N + 1 - l],h,1,N+2);
        int it2 = query(root[N + 1 - l],h + 1,1,N+2) - 1;


        int it3 = query(root[N + 1 - l1],h1,1,N+2);
        int it4 = query(root[N + 1 - l1],h1 + 1,1,N+2) - 1;


        if(it1 == it3 && it4 == it2){
            printf("%lld\n",min(h + (long long)l * (l - 1) / 2,h1 + (long long)l1 * (l1 - 1) / 2) );
            z = min(h + (long long)l * (l - 1) / 2,h1 + (long long)l1 * (l1 - 1) / 2);
            continue;
        }
        if(it1 <= it3 && it4 <= it2){
            printf("%lld\n",h + (long long)l * (l - 1) / 2 );
            z = h + (long long)l * (l - 1) / 2;
            continue;
        }
        if(it3 <= it1 && it2 <= it4){
            printf("%lld\n",h1 + (long long)l1 * (l1 - 1) / 2 );
            z = h1 + (long long)l1 * (l1 - 1) / 2;
            continue;
        }
//printf("test\n");
        h = mep[{it1,it2}];
        h1 = mep[{it3,it4}];

        if(d[h] > d[h1]) swap(h,h1);

        for(int j = 29; j >= 0; j--){
            if(parent[h1][j] != -1 && d[parent[h1][j]] >= d[h]) h1 = parent[h1][j];
        }

        if(h == h1){
            printf("%lld\n",ans[h]);
            z = ans[h];
            continue;
        }

        for(int j = 29; j >= 0; j--){
            if(parent[h1][j] != parent[h][j]){
                h1 = parent[h1][j];
                h = parent[h][j];
            }
        }

        h = parent[h][0];

        printf("%lld\n",ans[h]);
        z = ans[h];
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf(" %lld",&N);
      |     ~~~~~^~~~~~~~~~~~
Main.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf(" %d",&Q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     scanf(" %d",&t);
      |     ~~~~~^~~~~~~~~~
Main.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf(" %lld\n",&h);
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         scanf(" %lld",&h);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         scanf(" %lld",&h1);
      |         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60