QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #873896 | #9791. Intrusive Donkey | KryptonK | WA | 1ms | 3712kb | C++20 | 11.3kb | 2025-01-27 07:29:03 | 2025-01-27 07:29:04 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define F first
#define S second
using LL = long long;
using i64 = long long;
using pii = pair<int,int>;
using pil = pair<int,i64>;
using pli = pair<i64,int>;
using pll = pair<i64,i64>;
#define str string
// #define mp make_pair
#define eb emplace_back
#define pb push_back
#define si(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define LB lower_bound
#define UB upper_bound
#define i28 __int128
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
#define ar array
#ifndef ONLINE_JUDGE
#include "/Users/zonghong_0731/template/debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
//for loop
#define rep1(n) for(LL i=0; i<(LL)(n); ++i)
#define rep2(i,n) for(LL i=0; i<(LL)(n); ++i)
#define rep3(i,a,b) for(LL i=(LL)(a); i<(LL)(b); ++i)
#define rep4(i,a,b,c) for(LL i=(LL)(a); i<(LL)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(LL i=((LL)n)-1; i>=0; --i)
#define per2(i,n) for(LL i=((LL)n)-1; i>=0; --i)
#define per3(i,a,b) for(LL i=((LL)a)-1; i>=(LL)(b); --i)
#define per4(i,a,b,c) for(LL i=((LL)a)-1; i>=(LL)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define rep_subset(i,s) for(LL i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
template<class t> using vvvc = vc<vvc<t>>;
#define vv(type,name,n,...) \
vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
#define vvv(type,name,n,m,...) \
vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))
using vi = vc<int>;
using vl = vc<LL>;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }
//bit manipulation referenced from maroonrk
template<class T> int topbit(T t){return t==0?-1:63-__builtin_clzll(t);}
template<class T> int botbit(T t){return t==0?64:__builtin_ctzll(t);}
template<class T> int popcount(T t){return __builtin_popcountll(t);}
template<typename T> T gcd(T a,T b) {while (b > 0) {LL t = a % b; a = b; b = t;} return a;}
std::array<i64, 3> exgcd(i64 a, i64 b) {
if (!b) {
return {a, 1, 0};
}
auto [g, x, y] = exgcd(b, a % b);
return {g, y, x - a / b * y};
}
template<typename T, typename TT> istream& operator >> (istream& i, pair<T,TT> &p){return i >> p.F >> p.S;}
template<typename T, typename TT> ostream& operator << (ostream& o, const pair<T,TT> &p){return o << p.F << ' ' << p.S;}
//cin vc<T>
template<typename T> istream& operator >> (istream& i, vc<T> &v){for(auto &x: v) i >> x; return i;}
//print 管理
template<typename T> void W(vector<vector<T>>& x){for(auto i: x){ for(auto j: i){cout << j << ' ';} cout << "\n";}}
template<typename T> void W(vector<T>& x){rep(si(x)) cout << x[i] << " \n"[i == si(x) - 1];}
template<typename T> void W(set<T>& x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void W(unordered_set<T>& x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void W(T && x) {cout << x << "\n";}
template<typename T, typename... S> void W(T && x, S&&... y) {cout << x << ' ';W(y...);}
template<class T> void sort_uni(T& a) {
sort(all(a));
a.erase(unique(all(a)), a.end());
}
template<class T> LL MAX(T& a) {
return ranges::max(a);
}
template<class T> LL MIN(T& a) {
return ranges::min(a);
}
template<class T> LL SUM(T& a) {
return reduce(all(a), 0LL);
}
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
template <class t> using mxheap = priority_queue<t>;
template <class t> using mnheap = priority_queue<t,vc<t>,greater<t>>;
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template<class T>
constexpr T fpow(T a, u64 b, const LL MOD) {
T res {1};
while(b) {
if (b & 1) res = (res * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
const int inf = 1e9;
const LL linf = 2e18;
// LazySegtree referenced from jiangly
template<class Info, class Tag>
struct LazySegmentTree {
int n;
std::vector<Info> info;
std::vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size();
info.assign(4 << topbit(n), Info());
tag.assign(4 << topbit(n), Tag());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
push(p);
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l >= y || r <= x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n, l, r, v);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F pred) {
if (l >= y || r <= x || !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F pred) {
return findFirst(1, 0, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F pred) {
if (l >= y || r <= x || !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findLast(2 * p + 1, m, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F pred) {
return findLast(1, 0, n, l, r, pred);
}
void add(int id, int l, int r, int p, LL v) {
if (l == r - 1) {
info[id].sum += v;
return;
}
int mid = (l + r) >> 1;
push(id);
if (p < mid) {
add(id * 2, l, mid, p, v);
} else {
add(id * 2 + 1, mid, r, p, v);
}
pull(id);
}
};
struct Tag {
LL mul = 1;
void apply(Tag t) {
mul *= t.mul;
}
};
struct Info {
LL sum = 0;
void apply(Tag t) {
sum *= t.mul;
}
};
Info operator+(Info a, Info b) {
return {a.sum + b.sum};
}
void tsuyoku_nareru() {
int n, q;
cin >> n >> q;
str s;
cin >> s;
LazySegmentTree<Info, Tag> seg(n, {1});
LL sum = 0;
auto f = [&](Info& x) {
if (sum <= x.sum) {
return 1;
}
sum -= x.sum;
return 0;
};
while (q--) {
int op;
cin >> op;
if (op == 1) {
int l, r;
cin >> l >> r;
sum = l;
int lpos = seg.findFirst(0, n, f);
sum = r;
int rpos = seg.findFirst(0, n, f);
//debug(lpos, rpos);
if (lpos == rpos) {
seg.add(1, 0, n, lpos, r - l + 1);
} else {
if (lpos + 1 <= rpos - 1) {
seg.rangeApply(lpos + 1, rpos, {2});
}
LL ladd = seg.rangeQuery(0, lpos + 1).sum - l + 1;
LL radd = r - seg.rangeQuery(0, rpos).sum;
//debug(ladd, radd);
seg.add(1, 0, n, lpos, ladd);
seg.add(1, 0, n, rpos, radd);
}
} else {
int p;
cin >> p;
sum = p;
int pos = seg.findFirst(0, n, f);
//debug(pos);
W(s[pos]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
tsuyoku_nareru();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
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: 0ms
memory: 3712kb
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: 0ms
memory: 3712kb
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: 1ms
memory: 3584kb
input:
5 4 shrek 1 1 2 2 7 1 1 7 2 7
output:
k h
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3712kb
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 e f f f f v f e f f f e e e f e e f e e e f e f e v
result:
ok 27 lines
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3584kb
input:
60 51 ranhfkbjhkxckkcbhgsspsjcbjgpwcfvmqqlvlfualndmqqsihsfdyqviowu 2 53 2 37 2 33 2 60 1 1 32 2 44 1 87 92 1 7 77 1 56 86 2 17 1 128 184 1 26 159 2 323 2 55 1 24 316 1 435 652 2 316 2 444 1 819 868 2 27 2 912 2 313 1 555 576 1 510 942 1 1118 1269 2 365 2 84 1 595 650 2 1468 2 258 1 1557 1607 2 938 1...
output:
d v m u s r r r r r r r r r r r r r r r r r r r r r
result:
wrong answer 6th lines differ - expected: 'k', found: 'r'