Submission #1273728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273728		dzuizz	Poklon (COCI17_poklon)	C++20	140 / 140	674 ms	95616 KiB

poklon

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
  int l,r,m,v;
  node *lf,*rg;
  node(int _l,int _r): l(_l),r(_r),m((_l+_r)>>1),v(0) {
    if(l!=r)
      lf=new node(l,m),
      rg=new node(m+1,r);
  }
  void upd(int x,int _v){
    if(l==r){ v=_v; return; }
    if(x<=m) lf->upd(x,_v);
    else rg->upd(x,_v);
    v=lf->v+rg->v; 
  }
  int qry(int x,int y){
    //cout<<l<<" "<<r<<": "<<v<<'\n';
    if(r<x||l>y) return 0;
    if(x<=l&&r<=y) return v;
    return lf->qry(x,y)+rg->qry(x,y);
  }
}*root;
signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n,q; cin>>n>>q;
  int a[n],ta[n];
  for(int i=0;i<n;++i){
    cin>>a[i];
    ta[i]=a[i];
  }
  sort(ta,ta+n);
  for(int i=0,m=unique(ta,ta+n)-ta;i<n;++i)
    a[i]=lower_bound(ta,ta+m,a[i])-ta;
  int nx[n],occ[n];
  memset(nx,-1,sizeof nx);
  memset(occ,-1,sizeof occ);
  for(int i=0;i<n;++i){
    if(occ[a[i]]!=-1) nx[occ[a[i]]]=i;
    occ[a[i]]=i;
  }
  root=new node(0,n-1);
  bool vi[n]; memset(vi,0,sizeof vi);
  for(int i=0;i<n;++i){
    if(vi[a[i]]) continue;
    vi[a[i]]=1;
    if(nx[i]!=-1){
      root->upd(nx[i],1);
      if(nx[nx[i]]!=-1) root->upd(nx[nx[i]],-1);
    }
  }
  //for(int i=0;i<n;++i) cout<<root->qry(i,i)<<" "; cout<<'\n';
  pair<pair<int,int>,int> qrys[q];
  for(int i=0;i<q;++i){
    cin>>qrys[i].first.first>>qrys[i].first.second;
    qrys[i].second=i;
  }
  sort(qrys,qrys+q);
  int ans[q];
  for(int i=0,pl=0;i<q;++i){
    auto[l,r]=qrys[i].first; --l,--r;
    while(pl<l){
      if(nx[pl]!=-1){
        root->upd(nx[pl],0);
        if(nx[nx[pl]]!=-1){
          root->upd(nx[nx[pl]],1);
          if(nx[nx[nx[pl]]]!=-1)
            root->upd(nx[nx[nx[pl]]],-1);
        }
      }
      ++pl;
    }
    ans[qrys[i].second]=root->qry(l,r);
  }
  for(auto&x:ans) cout<<x<<'\n';
  return 0;
}

• Subtask 1: 140 / 140