제출 #1305348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305348		fangyj	Specijacija (COCI20_specijacija)	C++20	0 / 110	285 ms	509616 KiB

Main

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

const int MAXN=200005;
const int MAXNODE=MAXN*100;
const int LOG=19;
const int OFFSET=(1<<18);

struct Node {
    int val, cnt;
    Node *l, *r;
    Node() {val=cnt=0;l=r=this;}
    Node(int v,int c,Node* L,Node* R){val=v;cnt=c;l=L;r=R;}
};

int CNT;
Node nodes[MAXNODE];
Node* newNode(){
    nodes[CNT].l=nodes[CNT].r=&nodes[CNT];
    return &nodes[CNT++];
}

struct PST {
    Node* root[MAXN];
    PST(){for(int i=0;i<MAXN;i++) root[i]=newNode();}

    Node* update(Node* cur,int l,int r,int pos,int x){
        if(l>pos||r<pos) return cur;
        if(l==r){
            Node* tmp=newNode();
            tmp->val=x;
            tmp->cnt=(x!=0);
            return tmp;
        }
        int mid=(l+r)/2;
        Node* L=update(cur->l,l,mid,pos,x);
        Node* R=update(cur->r,mid+1,r,pos,x);
        Node* tmp=newNode();
        tmp->l=L; tmp->r=R; tmp->cnt=L->cnt+R->cnt;
        return tmp;
    }

    pair<int,int> kth(Node* cur,int l,int r,int k){
        if(l==r) return {l,cur->val};
        int mid=(l+r)/2;
        if(cur->l&&cur->l->cnt>=k) return kth(cur->l,l,mid,k);
        else return kth(cur->r,mid+1,r,k-(cur->l->cnt));
    }
}T;

struct Tree {
    int up[LOG][MAXN*2], dep[MAXN*2];
    vector<int> g[MAXN*2];

    void add(int a,int b){g[a].push_back(b);g[b].push_back(a);}
    void dfs(int u,int p,int d){dep[u]=d;for(int v:g[u]) if(v!=p){up[0][v]=u;dfs(v,u,d+1);}}
    void init(){for(int i=1;i<LOG;i++) for(int j=0;j<MAXN*2;j++) up[i][j]=up[i-1][up[i-1][j]];}
    int lca(int a,int b){
        if(dep[a]<dep[b]) swap(a,b);
        for(int i=LOG-1;i>=0;i--) if(dep[a]-(1<<i)>=dep[b]) a=up[i][a];
        if(a==b) return a;
        for(int i=LOG-1;i>=0;i--) if(up[i][a]!=up[i][b]) a=up[i][a],b=up[i][b];
        return up[0][a];
    }
}tree;

int n,q;
long long p[MAXN], val[MAXN*2];

int find(long long x){
    int lo=1,hi=n+1;
    while(lo!=hi){
        int mid=(lo+hi+1)/2;
        if((long long)mid*(mid-1)/2<x) lo=mid;
        else hi=mid-1;
    }
    int lvl=lo;
    int ind=(int)(x-(long long)lvl*(lvl-1)/2);
    return T.kth(T.root[lvl],0,OFFSET-1,ind).second;
}

long long query(long long a,long long b){
    int x=find(a), y=find(b);
    int l=tree.lca(x,y);
    return min(min(a,b),val[l]);
}

int main(){
    scanf("%d%d%d",&n,&q,&n);
    for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
    for(int i=0;i<=n;i++){
        val[i+1]=(long long)(n+1)*n/2+i+1;
        T.root[n+1]=T.update(T.root[n+1],0,OFFSET-1,i+1,i+1);
    }
    int nxt=n+2;
    for(int i=n;i>0;i--){
        int ind=(int)(p[i]-(long long)i*(i-1)/2);
        auto a=T.kth(T.root[i+1],0,OFFSET-1,ind);
        auto b=T.kth(T.root[i+1],0,OFFSET-1,ind+1);
        tree.add(a.second,nxt); tree.add(b.second,nxt);
        val[nxt]=p[i];
        T.root[i]=T.update(T.root[i+1],0,OFFSET-1,a.first,nxt++);
        T.root[i]=T.update(T.root[i],0,OFFSET-1,b.first,0);
    }
    tree.dfs(nxt-1,-1,0);
    tree.init();
    long long last=0, N=(long long)(n+1)*(n+2)/2;
    for(int i=0;i<q;i++){
        long long a,b;
        scanf("%lld%lld",&a,&b);
        long long A=(a-1+n*last)%N+1;
        long long B=(b-1+n*last)%N+1;
        long long ans=query(A,B);
        printf("%lld\n",ans);
        last=ans;
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d%d%d",&n,&q,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:90:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     for(int i=1;i<=n;i++) scanf("%lld",&p[i]);
      |                           ~~~~~^~~~~~~~~~~~~~
Main.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         scanf("%lld%lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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