//code by p1ckle/sft/yukicoder //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") //#pragma GCC target("avx,avx2") #include #define int long long int #define F first #define X first #define S second #define Y second #define mid ((start+end)/2) #define all(x) x.begin(), x.end() #define ub(a, b) upper_bound(all(a), b) #define lb(a, b) lower_bound(all(a), b) #define forf(a, b, c) for (int a = b; a <= c; a++) #define ford(a, b, c) for (int a = b; a < c; a++) #define forp(a, b) for (int a : b) #define pb push_back #define endl '\n' using namespace std; typedef vector vi; typedef pair pii; typedef vector> vpii; typedef long double ld; const int inf = 1e18, mod = 1e9+7, maxn = (1<<19)-1; vpii dr4 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, dr8 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}}; int q; struct node { node *l, *r; int v; node() {l = r = nullptr; v = 0;} }; node *root[maxn+3]; void init(node *cur, int start, int end) { if (start == end) return; cur->l = new node(); cur->r = new node(); init(cur->l, start, mid); init(cur->r, mid+1, end); } void updt(node *prv, node *cur, int start, int end, int tgt) { if (start == end) {cur->v++; return;} if (tgt <= mid) {cur->l = new node(); cur->r = prv->r; updt(prv->l, cur->l, start, mid, tgt);} else {cur->l = prv->l; cur->r = new node(); updt(prv->r, cur->r, mid+1, end, tgt);} cur->v = cur->l->v + cur->r->v; } int query2(node *scur, node *ecur, int start, int end, int val) { if (start == end) return start; if (val&((end-start+1)/2)) { //최상위비트가 1일때 -> 0을먹여야함 if (ecur->l->v-scur->l->v > 0) return query2(scur->l, ecur->l, start, mid, val); else return query2(scur->r, ecur->r, mid+1, end, val); } else { if (ecur->r->v-scur->r->v > 0) return query2(scur->r, ecur->r, mid+1, end, val); else return query2(scur->l, ecur->l, start, mid, val); } } int query4(node *scur, node *ecur, int start, int end, int left, int right) { if (start > right || end < left) return 0; if (start >= left && end <= right) return ecur->v - scur->v; return query4(scur->l, ecur->l, start, mid, left, right) + query4(scur->r, ecur->r, mid+1, end, left, right); } int query5(node *scur, node *ecur, int start, int end, int val) { if (start == end) return start; if (val-(ecur->l->v-scur->l->v) <= 0) return query5(scur->l, ecur->l, start, mid, val); else return query5(scur->r, ecur->r, mid+1, end, val-(ecur->l->v-scur->l->v)); } int cnt; int a, b, c, d; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> q; init(root[0] = new node(), 0, maxn); while (q--) { cin >> a >> b; if (a == 1) { cnt++; updt(root[cnt-1], root[cnt] = new node(), 0, maxn, b); } else if (a == 2) { cin >> c >> d; cout << query2(root[b-1], root[c], 0, maxn, d) << endl; } else if (a == 3) cnt -= b; else if (a == 4) { cin >> c >> d; cout << query4(root[b-1], root[c], 0, maxn, 0, d) << endl; } else { cin >> c >> d; cout << query5(root[b-1], root[c], 0, maxn, d) << endl; } } }

제출 #133299

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: