제출 #1221744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221744		emad234	Index (COCI21_index)	C++20	110 / 110	1076 ms	363964 KiB

index

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pii pair<int,int>
const int mod = 1e9 + 7;
const int mxN = (1 << 22) + 1;
using namespace std;
struct node{
  node *l,*r;
  int val;
  node(): l(0), r(0), val(0){}
  node(node* L, node* R, int V): l(L), r(R), val(V){}
};
int N;
vector<node*>root;
int query(int l, int r, int s,int e, node* cur){
  if(l > e || r < s) return 0;
  if(l >= s && r <= e) return cur->val;
  int op1 = 0,op2 = 0;
  int md = (l + r) / 2;
  if(cur->l != 0) op1 = query(l,md,s,e,cur->l);
  if(cur->r != 0) op2 = query(md + 1,r,s,e,cur->r);
  return op1 + op2;
}
node* update(int l,int r,int ind,int val, node* cur){
  if(l == r) return new node(cur->l,cur->r,cur->val + val);
  int md = (l + r) / 2;
  node *L = new node;
  node *R = new node;
  if(ind <= md) {
    L = update(l,md,ind,val,cur->l);
    R = cur->r;
  }else{
    L = cur->l;
    R = update(md + 1,r,ind,val,cur->r);
  }
  return new node(L,R,L->val + R->val);
}
node* build(int l,int r){
  if(l == r) return new node(nullptr,nullptr,0);
  node *cur = new node();
  int md = (l + r) / 2;
  cur->l = build(l,md);
  cur->r = build(md + 1,r);
  return cur;
}
int walk(int l,int r,node* st, node* ed){
  if(l == r) return l;
  int md = (l + r) / 2;
  // cout<<l<<' '<<r<<' '<<query(1,N,md + 1,N,ed)<<' '<<query(1,N,md + 1,N,st)<<'\n';
  if(query(1,N,md + 1,N,ed) - query(1,N,md + 1,N,st) >= md + 1) return walk(md + 1,r,st,ed);
  return walk(l,md,st,ed);
}
void printseg(node* cur){
  int cnt = 0;
  int ex = 1;
  queue<node*>q;
  q.push(cur);
  while(q.size()){
    cnt++;
    auto u = q.front();
    q.pop();
    cout<<u->val<<' ';
    if(ex * 2 - 1 == cnt){
      cout<<'\n';
      ex *= 2;
    }
    if(u->l != 0) q.push(u->l);
    if(u->r != 0) q.push(u->r);
  }
}
signed main(){
  int n,q;
  cin >>n>>q;
  N = exp2(ceil(log2(n)));
  root.push_back(build(1,N));
  for(int i = 1;i <= n;i++){
    int x;
    cin >>x;
    root.push_back(update(1,N,x,1,root.back()));
  }
  // for(auto x : root){
  //   printseg(x);
  //   cout<<'\n';
  // }
  while(q--){
    int x,y;
    cin >>x>>y;
    // printseg(root[x - 1]);
    // cout<<'\n';
    // printseg(root[y]);
    // cout<<'\n';
    cout<<walk(1,N,root[x - 1],root[y])<<'\n';
  }
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50