QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #775169 | #9791. Intrusive Donkey | ucup-team4893# | WA | 1ms | 3648kb | C++17 | 2.7kb | 2024-11-23 14:56:47 | 2024-11-23 14:56:48 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define maxn 200005
#define fopen(x, y) freopen(x".in", "r", stdin); freopen(y".out", "w", stdout);
#define int long long
#ifdef int
#define inf 0x3f3f3f3f3f3f3f3fll
#else
#define inf 0x3f3f3f3f
#endif
using namespace std;
int n, q, op, l, r, x, lm = 1000000000000000000ll;
string s;
void mul(int &x, int y) {
if(lm / x < y) x = lm;
else x *= y;
}
struct sgt {
struct node {
int l, r, sum, tag;
} a[maxn * 4];
void build(int id, int l, int r) {
a[id] = {l, r, 1, 1};
if(l == r) return ;
int mid = (a[id].l + a[id].r) >> 1;
build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r);
a[id].sum = a[id * 2].sum + a[id * 2 + 1].sum;
}
void inh(int id) {
if(a[id].l == a[id].r) return ;
int lch = id * 2, rch = lch + 1;
mul(a[lch].sum, a[id].tag);
mul(a[lch].tag, a[id].tag);
mul(a[rch].sum, a[id].tag);
mul(a[rch].tag, a[id].tag);
a[id].tag = 1;
}
void modify(int id, int l, int r) {
if(a[id].l == l && a[id].r == r) {
mul(a[id].tag, 2);
mul(a[id].sum, 2);
return ;
}
inh(id);
int mid = (a[id].l + a[id].r) >> 1;
if(r <= mid) modify(id * 2, l, r);
else if(l > mid) modify(id * 2 + 1, l, r);
else modify(id * 2, l, mid), modify(id * 2 + 1, mid + 1, r);
a[id].sum = min(a[id * 2].sum + a[id * 2 + 1].sum, lm);
}
void add(int id, int x, int v) {
if(a[id].l == x && a[id].r == x) {
a[id].sum += v;
return ;
}
inh(id);
int mid = (a[id].l + a[id].r) >> 1;
if(x <= mid) add(id * 2, x, v);
else add(id * 2 + 1, x, v);
a[id].sum = min(a[id * 2].sum + a[id * 2 + 1].sum, lm);
}
int query(int id, int l, int r) {
if(l > r) return 0;
if(a[id].l == l &&a[id].r == r) {
return a[id].sum;
}
int mid = (a[id].l + a[id].r) >> 1;
if(r <= mid) return query(id * 2, l, r);
else if(l > mid) return query(id * 2 + 1, l, r);
else {
int s1 = query(id * 2, l, mid), s2 = query(id * 2 + 1, mid + 1, r);
if(s1 + s2 <= lm) return s1 + s2; return lm;
}
}
int um_nik(int id, int s) {
if(a[id].l == a[id].r) return a[id].l;
inh(id);
if(a[id * 2].sum >= s) return um_nik(id * 2, s);
else return um_nik(id * 2 + 1, s - a[id * 2].sum);
}
} g;
void work() {
cin >> n >> q >> s;
s = " " + s;
g.build(1, 1, n);
while(q--) {
cin >> op;
if(op == 1) {
cin >> l >> r;
int L = g.um_nik(1, l), R = g.um_nik(1, r), lsum = g.query(1, 1, L), rsum = g.query(1, 1, R - 1);
if(L + 1 < R) g.modify(1, L + 1, R - 1);
g.add(1, L, lsum - l + 1);
g.add(1, R, r - rsum);
}
else {
cin >> x;
cout << s[g.um_nik(1, x)] << '\n';
}
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int _ = 1;
// cin >> _;
while(_--) work();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3512kb
input:
4 7 abac 2 2 2 3 1 2 3 2 3 2 4 2 5 2 6
output:
b a b a a c
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
5 4 shrek 1 1 2 2 7 1 1 7 2 7
output:
k h
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
4 7 abac 2 2 2 3 1 2 3 2 3 2 4 2 5 2 6
output:
b a b a a c
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
5 4 shrek 1 1 2 2 7 1 1 7 2 7
output:
k h
result:
ok 2 lines
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3584kb
input:
3 55 vfe 1 2 3 1 2 2 1 3 5 2 4 1 1 2 2 9 2 7 2 5 1 10 10 1 1 1 2 9 1 8 12 2 8 1 7 10 2 1 1 5 6 1 1 4 1 20 24 1 14 32 1 19 38 2 48 1 56 64 2 58 2 19 1 64 72 1 36 86 2 11 1 117 124 2 38 2 108 2 85 1 112 118 2 153 2 40 2 114 2 80 1 11 18 2 27 2 73 1 159 162 2 84 1 130 164 2 163 2 65 1 150 156 1 101 109...
output:
f f f f f f v f f v v f f f f f f f v f f f f f v f v
result:
wrong answer 2nd lines differ - expected: 'e', found: 'f'