QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#768056	#9559. The Tower	hos_lyric	AC ✓	737ms	965504kb	C++14	4.4kb	2024-11-21 00:01:23	2024-11-21 00:01:35

Judging History

你现在查看的是最新测评结果

[2024-11-21 00:01:35]
评测

测评结果：AC
用时：737ms
内存：965504kb

查看

[2024-11-21 00:01:23]
提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// always full binary tree

constexpr int MAX = 40 << 20;  // 960 MB
int no, ls[MAX], rs[MAX], lls[MAX], rrs[MAX], par[MAX], sz[MAX];
int New(int sz_) { const int u = no++; ls[u] = rs[u] = par[u] = lls[u] = rrs[u] = 0; sz[u] = sz_; return u; }

void init() { no = 1; }
void pull(int u) { par[ls[u]] = par[rs[u]] = u; sz[u] = sz[ls[u]] + sz[rs[u]]; }
// w: global segtree
void split(int &u, int &v, int &w, int l, int r, int k) {
// cerr<<"[split] "<<u<<" "<<v<<" "<<w<<" "<<l<<" "<<r<<" "<<k<<endl;
  v = New(0);
  if (k == 0) return;
  if (k >= sz[u]) { swap(u, v); return; }
  if (!ls[u]) ls[u] = lls[w] = New((r-l)/2);
  if (!rs[u]) rs[u] = rrs[w] = New((r-l)/2);
  const int m = l+(r-l)/2, kL = min(k, sz[ls[u]]);
  split(ls[u], ls[v], lls[w], l, m, kL);
  split(rs[u], rs[v], rrs[w], m, r, k - kL);
  pull(u); pull(v);
}
int merge(int u, int v) {
  if (!sz[u]) return v;
  if (!sz[v]) return u;
  ls[u] = merge(ls[u], ls[v]);
  rs[u] = merge(rs[u], rs[v]);
  pull(u);
  return u;
}
int query(int w, int l, int r, int pos) {
  if (!w) return 0;
  const int m = l+(r-l)/2;
  const int u = (pos < m) ? query(lls[w], l, m, pos) : query(rrs[w], m, r, pos);
  return u ? u : w;
}
void print(int u, int l, int r, int dep = 0) {
  if (!u) return;
  printf("%su=%d [l,r)=[%d,%d) sz=%d par=%d\n", string(2*dep, ' ').c_str(), u, l, r, sz[u], par[u]);
  const int m = l+(r-l)/2;
  print(ls[u], l, m, dep + 1);
  print(rs[u], m, r, dep + 1);
}
void printt(int u, int l, int r, int dep = 0) {
  if (!u) return;
  printf("%su=%d [l,r)=[%d,%d) sz=%d par=%d\n", string(2*dep, ' ').c_str(), u, l, r, sz[u], par[u]);
  const int m = l+(r-l)/2;
  printt(lls[u], l, m, dep + 1);
  printt(rrs[u], m, r, dep + 1);
}

#ifdef LOCAL
constexpr int L = 1;
// constexpr int R = 1 + (1<<3);
constexpr int R = 1 + (1<<6);
#else
constexpr int L = 1;
constexpr int R = 1 + (1<<30);
#endif

int main() {
  int Q;
  for (; ~scanf("%d", &Q); ) {
    vector<int> us;
    map<int, int> invUs;
    init();
    us.push_back(0);
    us[0] = New(R-L);
    invUs[us[0]] = 0;
    int w = us[0];
    for (; Q--; ) {
      int O;
      scanf("%d", &O);
      if (O == 1) {
        int K;
        scanf("%d", &K);
        const int i = us.size();
// cerr<<COLOR("91")<<"add i="<<i<<" K="<<K<<COLOR()<<endl;
        us.push_back(0);
        invUs.erase(us[0]);
        split(us[0], us[i], w, L, R, K);
        invUs[us[0]] = 0;
        invUs[us[i]] = i;
      } else if (O == 2) {
        int i;
        scanf("%d", &i);
// cerr<<COLOR("94")<<"rem i="<<i<<COLOR()<<endl;
        invUs.erase(us[0]);
        invUs.erase(us[i]);
        us[0] = merge(us[0], us[i]);
        us[i] = 0;
        invUs[us[0]] = 0;
      } else if (O == 3) {
        int X;
        scanf("%d", &X);
        int u = query(w, L, R, X);
// cerr<<COLOR("93")<<"query X="<<X<<": u="<<u<<COLOR()<<endl;
        for (; par[u]; u = par[u]) {}
        printf("%u\n", invUs[u]);
      } else {
        assert(false);
      }
if(0)if(O!=3){
 cerr<<"us = "<<us<<", w = "<<w<<endl;
 for(const int u:us)print(u,L,R);
 cerr<<COLOR("92");printt(w,L,R);cerr<<COLOR();
 cerr<<endl;
}
    }
  }
  return 0;
}

Source code, Language: C++14

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 14340kb

input:

output:

2
0
3

result:

ok 3 number(s): "2 0 3"

Test #2:

score: 0

Accepted

time: 2ms

memory: 14028kb

input:

output:

0
0
1

result:

ok 3 number(s): "0 0 1"

Test #3:

score: 0

Accepted

time: 0ms

memory: 14156kb

input:

output:

result:

ok 164 numbers

Test #4:

score: 0

Accepted

time: 2ms

memory: 14108kb

input:

500
3 1
3 1
3 1
3 1
3 1
1 4412412
1 10247266
1 14616289
3 13925896
1 44094358
2 4
3 16963583
1 29167079
1 71445446
3 121523866
1 9541088
2 6
2 7
3 143236216
2 2
3 156313828
1 33267424
3 100714325
3 15092860
3 89601770
2 8
3 201789970
1 30507527
2 5
1 67021830
3 234973560
1 10823444
1 19147051
1 7218...

output:

result:

ok 174 numbers

Test #5:

score: 0

Accepted

time: 0ms

memory: 14072kb

input:

500
3 1
3 1
3 1
1 320269189
1 948169162
1 351870928
1 913315720
2 4
1 165426182
1 539661032
3 842094943
3 726768630
1 585756645
1 327182255
3 928037381
3 819034974
3 749190162
3 676969663
2 2
1 802722944
1 848855782
3 227383778
1 725550812
3 892603437
1 451994900
3 470357939
2 1
1 598424975
3 786248...

output:

result:

ok 173 numbers

Test #6:

score: 0

Accepted

time: 2ms

memory: 14048kb

input:

output:

0
1

result:

ok 2 number(s): "0 1"

Test #7:

score: 0

Accepted

time: 320ms

memory: 220956kb

input:

output:

result:

ok 167358 numbers

Test #8:

score: 0

Accepted

time: 266ms

memory: 75896kb

input:

500000
3 1
1 34999032
2 1
3 20479366
3 16132210
3 10950706
3 27656988
3 18181558
3 20096893
1 83795773
3 113805204
3 115628116
1 42488647
1 42211622
2 3
1 92268056
2 2
1 80060142
2 4
1 49696107
3 299966231
3 365132652
1 46139635
1 64375123
2 8
3 39930760
1 14908781
3 210153892
1 85648326
3 568835561...

output:

result:

ok 166515 numbers

Test #9:

score: 0

Accepted

time: 159ms

memory: 27692kb

input:

500000
3 1
3 1
3 1
1 85593529
3 57891556
2 1
3 38559908
1 727251945
1 815334095
1 988926819
3 107155104
1 724052442
3 63908582
2 5
2 4
1 84610655
2 2
3 2423402
3 853118582
1 448879846
2 6
2 3
1 815614446
2 8
1 674635945
2 7
1 46140898
3 820338862
2 10
1 692524546
2 11
1 625079933
1 482471788
3 44351...

output:

result:

ok 166286 numbers

Test #10:

score: 0

Accepted

time: 305ms

memory: 52336kb

input:

500000
1 39567744
1 957918384
1 896336073
1 302217145
1 328404139
1 984894105
1 428308004
1 67268263
1 619517065
1 186724562
1 165376000
1 253795867
1 721330183
1 433623064
1 20169195
1 288503667
1 791272786
1 526657641
1 638212274
1 501209932
1 320898519
1 288747265
1 581193313
1 497930627
1 423401...

output:

result:

ok 0 number(s): ""

Test #11:

score: 0

Accepted

time: 583ms

memory: 832812kb

input:

output:

result:

ok 25227 numbers

Test #12:

score: 0

Accepted

time: 737ms

memory: 424172kb

input:

output:

result:

ok 49640 numbers

Test #13:

score: 0

Accepted

time: 208ms

memory: 29468kb

input:

500000
1 325663181
1 341421661
2 1
2 2
1 798695561
1 789604791
2 3
1 752705846
1 271837520
1 2324300
1 156465725
1 552978643
1 704305136
3 708781692
1 538026101
1 554055497
1 551799143
1 928267539
1 162992249
1 178671365
1 41327601
1 34105375
3 583284520
2 4
1 335357707
2 18
2 13
1 351743555
2 11
1 ...

output:

result:

ok 49895 numbers

Test #14:

score: 0

Accepted

time: 677ms

memory: 469332kb

input:

output:

result:

ok 224721 numbers

Test #15:

score: 0

Accepted

time: 205ms

memory: 28204kb

input:

output:

result:

ok 495045 numbers

Test #16:

score: 0

Accepted

time: 730ms

memory: 371752kb

input:

output:

result:

ok 9965 numbers

Test #17:

score: 0

Accepted

time: 277ms

memory: 39188kb

input:

500000
3 863503832
3 285813354
3 414051174
3 97666985
3 466272422
3 448257369
3 956137762
3 387839447
3 504996933
3 971922171
3 737655581
3 914663293
3 431235168
3 598801556
3 197441204
1 9085
3 18435039
1 28953
3 240290602
3 660593544
3 278294539
3 760061094
3 947453399
3 182070243
3 222738570
3 93...

output:

result:

ok 460003 numbers

Test #18:

score: 0

Accepted

time: 3ms

memory: 14052kb

input:

5
1 1000000000
2 1
3 1000000000
1 1000000000
3 1000000000

output:

0
2

result:

ok 2 number(s): "0 2"

Test #19:

score: 0

Accepted

time: 0ms

memory: 14132kb

input:

1
3 11451419

output:

result:

ok 1 number(s): "0"

Test #20:

score: 0

Accepted

time: 628ms

memory: 278904kb

input:

500000
1 469
1 27403
1 8011
1 3666
3 431375941
1 5586
1 2876
1 911
1 8549
1 5022
1 11870
1 13676
1 14008
1 7714
1 5558
1 23433
1 5420
1 6330
1 1234
1 21150
1 15806
1 10289
1 638
1 1291
1 5427
1 304
1 7921
1 5709
1 586
1 3002
1 12144
1 5379
1 21367
1 10314
1 15571
1 21493
1 2691
1 7216
1 762
1 7791
1...

output:

result:

ok 20003 numbers

Test #21:

score: 0

Accepted

time: 573ms

memory: 280324kb

input:

output:

24734
167977
249999

result:

ok 3 number(s): "24734 167977 249999"

Test #22:

score: 0

Accepted

time: 618ms

memory: 309936kb

input:

500000
1 471049
3 210537770
3 174642262
3 409419351
1 117066
1 33053
1 13142
3 181598847
1 129357
1 37381
1 197686
3 478570811
1 58776
1 14683
1 151018
3 51491818
1 138638
1 85547
1 188477
1 757
1 3848
1 53283
1 77145
1 29393
1 91077
1 132182
3 167622476
1 110618
1 29202
1 133185
1 33985
3 436250120...

output:

result:

ok 200002 numbers

Test #23:

score: 0

Accepted

time: 725ms

memory: 471036kb

input:

output:

result:

ok 10002 numbers

Test #24:

score: 0

Accepted

time: 547ms

memory: 644784kb

input:

output:

result:

ok 101 numbers

Test #25:

score: 0

Accepted

time: 521ms

memory: 665644kb

input:

output:

result:

ok 6 numbers

Test #26:

score: 0

Accepted

time: 508ms

memory: 351144kb

input:

output:

result:

ok 50000 numbers

Test #27:

score: 0

Accepted

time: 454ms

memory: 302768kb

input:

output:

result:

ok 100000 numbers

Test #28:

score: 0

Accepted

time: 509ms

memory: 377252kb

input:

output:

result:

ok 106787 numbers

Test #29:

score: 0

Accepted

time: 443ms

memory: 465480kb

input:

output:

result:

ok 19985 numbers

Test #30:

score: 0

Accepted

time: 142ms

memory: 14504kb

input:

output:

result:

ok 499516 numbers

Test #31:

score: 0

Accepted

time: 233ms

memory: 39272kb

input:

output:

result:

ok 489886 numbers

Test #32:

score: 0

Accepted

time: 285ms

memory: 64880kb

input:

output:

result:

ok 474862 numbers

Test #33:

score: 0

Accepted

time: 552ms

memory: 965504kb

input:

output:

result:

ok 64 numbers

Test #34:

score: 0

Accepted

time: 64ms

memory: 14048kb

input:

output:

result:

ok 500000 numbers

Test #35:

score: 0

Accepted

time: 116ms

memory: 14348kb

input:

500000
1 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 1000000000
3 10000...

output:

result:

ok 499999 numbers

Extra Test:

score: 0

Extra Test Passed