結果

問題 No.1526 Sum of Mex 2
ユーザー 👑 NachiaNachia
提出日時 2021-05-31 20:28:57
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,048 ms / 3,000 ms
コード長 4,301 bytes
コンパイル時間 2,904 ms
コンパイル使用メモリ 216,252 KB
実行使用メモリ 43,136 KB
最終ジャッジ日時 2024-04-26 08:17:06
合計ジャッジ時間 22,438 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 123 ms
8,576 KB
testcase_14 AC 150 ms
11,776 KB
testcase_15 AC 191 ms
12,672 KB
testcase_16 AC 983 ms
41,984 KB
testcase_17 AC 672 ms
37,888 KB
testcase_18 AC 69 ms
7,680 KB
testcase_19 AC 57 ms
5,760 KB
testcase_20 AC 402 ms
21,888 KB
testcase_21 AC 925 ms
41,600 KB
testcase_22 AC 523 ms
23,936 KB
testcase_23 AC 969 ms
42,112 KB
testcase_24 AC 1,024 ms
42,624 KB
testcase_25 AC 948 ms
41,600 KB
testcase_26 AC 990 ms
42,240 KB
testcase_27 AC 1,016 ms
42,496 KB
testcase_28 AC 1,048 ms
42,752 KB
testcase_29 AC 1,011 ms
42,624 KB
testcase_30 AC 1,036 ms
43,008 KB
testcase_31 AC 1,021 ms
42,880 KB
testcase_32 AC 977 ms
42,112 KB
testcase_33 AC 954 ms
43,136 KB
evil_largest TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)


template<
  class S,
  S(*op)(S l,S r),
  S(*e)(),
  class F,
  S(*mapping)(F f,S a),
  F(*composition)(F f,F g),
  F(*id)(),
  bool(*beats)(S a)
>
struct segtreebeats{
private:
  struct Node{ S v; F r; };
  int N,logN;
  vector<Node> V;

  void mapF(int i,F f){
    V[i].v = mapping(f,V[i].v);
    V[i].r = composition(f,V[i].r);
    if(beats(V[i].v)){ spread(i); merge(i); }
  }
  void merge(int i){
    V[i].v = mapping(V[i].r,op(V[i*2].v,V[i*2+1].v));
  }
  void spread(int i){
    mapF(i*2,V[i].r); mapF(i*2+1,V[i].r);
    V[i].r=id();
  }
public:

  segtreebeats(int n){
    N=1; logN=0; while(N<n){ N*=2; logN++; }
    V.assign(N*2,{ e(),id() });
  }
  segtreebeats(vector<S> A) : segtreebeats(A.size()){
    rep(i,A.size()) V[N+i].v=A[i];
    for(int i=N-1; i>=1; i--) merge(i);
  }

  void set(int p,S v){
    p+=N;
    for(int d=logN; d>=1; d--) spread(p>>d);
    V[p].v=v;
    for(int d=1; d<=logN; d++) merge(p>>d);
  }
  S get(int p){
    p+=N;
    for(int d=logN; d>=1; d--) spread(p>>d);
    return V[p].v;
  }

  S prod(int l,int r){
    l+=N; r+=N;
    for(int d=logN; d>=1; d--){ spread(l>>d); spread((r-1)>>d); }
    S ql=e(), qr=e();
    while(l<r){
      if(l&1) ql=op(ql,V[l++].v);
      if(r&1) qr=op(V[--r].v,qr);
      l/=2; r/=2;
    }
    return op(ql,qr);
  }
  void apply(int p,F f){
    p+=N;
    for(int d=logN; d>=1; d--) spread(p>>d);
    mapF(p,f);
    for(int d=1; d<=logN; d++) merge(p>>d);
  }
  void apply(int l,int r,F f){
    l+=N; r+=N;
    for(int d=logN; d>=1; d--){ spread(l>>d); spread((r-1)>>d); }
    int lp=l, rp=r;
    while(l<r){
      if(l&1) mapF(l++,f);
      if(r&1) mapF(--r,f);
      l/=2; r/=2;
    }
    for(int d=1; d<=logN; d++){ merge(lp>>d); merge((rp-1)>>d); }
  }
};

struct cin_improve_speed{
  cin_improve_speed(){
    cin.tie(nullptr);
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
  }
} cin_improve_speed_instance;

const LL INF=2000000000000000000;
struct RCAS_S { LL l,lc,l2,r,rc,r2,s,z; bool beats; };
RCAS_S RCAS_op(RCAS_S l, RCAS_S r){
  RCAS_S res;
  res.l=min(l.l,r.l);
  res.lc=((l.l==res.l)?l.lc:0)+((r.l==res.l)?r.lc:0);
  res.l2=min(((l.l==res.l)?l.l2:l.l),((r.l==res.l)?r.l2:r.l));
  res.r=max(l.r,r.r);
  res.rc=((l.r==res.r)?l.rc:0)+((r.r==res.r)?r.rc:0);
  res.r2=max(((l.r==res.r)?l.r2:l.r),((r.r==res.r)?r.r2:r.r));
  res.s=l.s+r.s;
  res.z=l.z+r.z;
  res.beats=false;
  return res;
}
RCAS_S RCAS_e() { return { INF,0,INF,-INF,0,-INF,0,0,false }; }
struct RCAS_F { LL l,r,a; };
RCAS_S RCAS_mapping(RCAS_F f, RCAS_S a) {
  if(a.l2<=f.l){ a.beats=true; return a; }
  if(a.r2>=f.r){ a.beats=true; return a; }
  if(a.l<f.l){ a.s+=(f.l-a.l)*a.lc; if(a.r==a.l) a.r=f.l; if(a.r2==a.l) a.r2=f.l; a.l=f.l; }
  if(a.r>f.r){ a.s+=(f.r-a.r)*a.rc; if(a.l==a.r) a.l=f.r; if(a.l2==a.r) a.l2=f.r; a.r=f.r; }
  a.s+=f.a*a.z; if(a.l!=INF) a.l+=f.a; if(a.l2!=INF) a.l2+=f.a; if(a.r!=INF) a.r+=f.a; if(a.r2!=-INF) a.r2+=f.a;
  a.beats=false;
  return a;
}
RCAS_F RCAS_composition(RCAS_F f, RCAS_F g) {
  f.l-=g.a; f.r-=g.a;
  g.a+=f.a;
  g.l=min(max(g.l,f.l),f.r);
  g.r=min(max(g.r,f.l),f.r);
  return g;
}
RCAS_F RCAS_id() { return { -INF,INF,0 }; }
bool RCAS_beats(RCAS_S a){ return a.beats; }
using RCAS = segtreebeats<
  RCAS_S,
  RCAS_op,
  RCAS_e,
  RCAS_F,
  RCAS_mapping,
  RCAS_composition,
  RCAS_id,
  RCAS_beats
>;


RCAS_S uni(int v){
  RCAS_S res = RCAS_e();
  res.beats = false;
  res.l = res.r = res.s = v;
  res.lc = res.rc = 1;
  return res;
}


int main(){
  int N; cin >> N;
  vector<int> A(N);
  vector<int> prevbuf(N,0);
  vector<int> prev(N);
  for(int i=0; i<N; i++){ cin >> A[i]; A[i]--; }
  for(int i=0; i<N; i++){
    prev[i] = prevbuf[A[i]];
    prevbuf[A[i]] = i+1;
  }
  vector<RCAS_S> V(N); rep(i,N){ LL a = prevbuf[i]+1; V[i]={a,1,INF,a,1,-INF,a,1,false}; }
  RCAS G(V);
  LL ans = 0;
  for(int i=0; i<N; i++) G.apply(i,N,{-INF,prevbuf[i],0});
  for(int i=N-1; i>=0; i--){
    LL s = G.prod(0,N).s;
    ans += s;
    ans += i+1;
    G.apply(A[i],N,{-INF,prev[i],0});
  }
  cout << ans << "\n";
  return 0;
}



struct ios_do_not_sync{
  ios_do_not_sync(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  }
} ios_do_not_sync_instance;
0