QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

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

[2024-11-23 14:56:48]
评测

测评结果：WA
用时：1ms
内存：3648kb

查看

[2024-11-23 14:56:47]
提交

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();
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3512kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 1ms

memory: 3648kb

input:

output:

k
h

result:

ok 2 lines

Test #3:

score: 0

Accepted

time: 1ms

memory: 3572kb

input:

output:

b
a
b
a
a
c

result:

ok 6 lines

Test #4:

score: 0

Accepted

time: 0ms

memory: 3628kb

input:

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'