QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #610136 | #5452. Tractor Paths | Dimash# | 6.25 | 2ms | 11844kb | C++23 | 3.6kb | 2024-10-04 15:00:41 | 2024-10-04 15:00:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 12, MOD = (int)1e9 + 7;
int n, q, d[N], up[N][19], l = 19, c[N][19], dep[N];
pair<int, int> t[N * 4];
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
if(tl == tr) {
t[v].first = val;
t[v].second = tl;
} else {
int tm = (tl + tr) >> 1;
if(pos <= tm) upd(pos, val, v + v, tl, tm);
else upd(pos, val, v + v + 1, tm + 1, tr);
t[v] = max(t[v + v], t[v + v + 1]);
}
}
int dist(int v, int u) {
if(v == u) return 0;
int ret = 1;
for(int i = l - 1; i >= 0;i--) {
if(up[v][i] < u) {
ret += (1 << i);
v = up[v][i];
}
}
return ret;
}
pair<int, int> get(int l, int r, int v = 1, int tl = 1, int tr = n) {
if(l > r || tl > r || l > tr) return make_pair(-1e9, -1e9);
if(tl >= l && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}
bool ok[N];
pair<int, int> solve(int v, int u) {
int ret = dist(v, u), col = 0;
int V = v;
while(v) {
int r = min(u, up[v][0]);
if(ok[v]) {
col++;
}
for(int j = v + 1; j < r; j++) {
if(ok[j]) {
if(dist(V, j) + dist(j, u) == ret) {
assert(r != u);
assert(j + d[j] >= min(u, up[r][0]));
col++;
}
}
}
v = r;
if(r == u) break;
}
// for(int i = l - 1; i >= 0;i--) {
// if(up[v][i] < u) {
// ret += (1 << i);
// col += c[v][i];
// v = up[v][i];
// }
// }
// if(ok[v]) col++;
if(ok[u]) col++;
return make_pair(ret, col);
}
string s;
vector<int> vert[N];
void prec() {
int it = 1, col = 0;
for(int i = 1; i <= n + n; i++) {
char x = s[i - 1];
if(x == 'R') {
col--;
d[it++] = col;
} else {
col++;
}
}
upd(n, n);
for(int i = 0; i < l; i++) {
up[n][i] = n;
}
for(int i = n - 1; i >= 1;i--) {
int j = get(i + 1, i + d[i]).second;
dep[i] = dep[j] + 1;
up[i][0] = j;
for(int k = 1; k < 19; k++) {
up[i][k] = up[up[i][k - 1]][k - 1];
}
upd(i, i + d[i]);
}
for(int i = 1; i <= n; i++) {
if(ok[i]) vert[dep[i]].push_back(i);
}
for(int i = 1; i <= n - 1; i++) {
int j = up[i][0];
int L = upper_bound(vert[dep[j]].begin(), vert[dep[j]].end(), i) - vert[dep[j]].begin();
int R = lower_bound(vert[dep[j]].begin(), vert[dep[j]].end(), j) - vert[dep[j]].begin();
c[i][0] = R - L + ok[i];
}
for(int i = 1; i < l; i++) {
for(int j = 1; j <= n; j++) {
c[j][i] = c[j][i - 1] + c[up[j][i - 1]][i - 1];
}
}
}
vector<int> sp;
void test() {
cin >> n >> q >> s;
if(n > 5000) return;
for(int i = 1; i <= n; i++) {
char x;
cin >> x;
if(x == '1') {
ok[i] = 1;
sp.push_back(i);
}
}
prec();
while(q--) {
int a, b;
cin >> a >> b;
auto [res, c] = solve(a, b);
cout << res << ' ' << c << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 6.25
Accepted
time: 0ms
memory: 11844kb
input:
8 10 LLLLRLLLLRRRRRRR 11011010 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 3 2 4 2 5
output:
1 2 1 1 1 2 2 4 2 3 2 4 2 3 1 1 1 2 1 2
result:
ok 20 numbers
Test #2:
score: 0
Runtime Error
input:
5000 5000 LLRLRLRLRLRLRLRLLLRLRRLLRRRLRLLLRRRLRLLLRRRLLRRLRLRLLRRLRLLRRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLLRLRRLRLRLLRRLRLRLRLRLRLRLRLLRRLRLRLRLLRLRLRLLRRRLRLRLRLRLRLRLRLRLLLLRRRLRLRRLRLRLRLRLLRLLRRRLRLRLRLRLLRLRRLRLRLRLRLRLLLRRRLRLLRRLLRRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLLRLRRLRLRLRLRLRLRLRLRLLR...
output:
result:
Test #3:
score: 0
Runtime Error
input:
5000 5000 LLRLRLRLRLLLLLRRRRLRRLRLLRLRRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLLRRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLLRRLRLRLRLRLLRRLRLRLRLLRRLRLLRRLRLRLRLLRRLRLLRLLLLRRRLRRRLRLRLLRRLRLLLRLRRRLRLRLRLLRRLRLRLRLRLRLLRRLRLLRRLLRRLRLRLRLLLRRRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLLRRLRLLRLLRLRRLRRLRLRLRLLRRLRLRLRLRLRL...
output:
result:
Test #4:
score: 0
Wrong Answer
time: 2ms
memory: 3844kb
input:
200000 200000 LLLRRLRLRLRLRLRLRLRLRLRLLRLRRLRLLRRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLLRRLRLRLLRRLRLLRRLRLRLLRLRRLRLRLRLRLRLRLLRRLRLRLLRLRLRRLRLRLLRRLRLLRRLRLLRRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLLRRLRLRLRLLRRLLRRLRLRLLRRLLRRLRLRLRLRLRLRLRLRLRLRLLRRLLR...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #5:
score: 0
Wrong Answer
time: 2ms
memory: 3792kb
input:
200000 200000 LLRLRLRLLRLRRLRLRLRLLRRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLLRLLRRLRRLRLRLRLLRRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLRLRLRLRLLRRLRLRLRLRLLRRLRLRLRLRLRLLRRLRLLLRLRRRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLLRRLLRRLLRLRLRRLLRLLLRRRRLRLRLRLRLLRRLLRLRRLRLRLRLRLRLLLRRRLRLRLRLRLRLRLRLLLRRLLLRRRRL...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #6:
score: 0
Wrong Answer
time: 2ms
memory: 3784kb
input:
200000 200000 LLLRRLRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLLRRRLRLRLLLRRRLRLLRLLLRRRLRRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLLRRLLLRRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLLRRLRLRLRLRLRLLRRLRLLRRLRLRLRLRLLRRLRLLRRLLRRLRLRLRLRLRLLLRRLRLRRLRLRLLR...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #7:
score: 0
Wrong Answer
time: 2ms
memory: 3736kb
input:
200000 200000 LLLRRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLLLRRRLRLRLLRRLLRRLLRRLRLLLRRRLRLRLRLRLRLRLRLRLRLRLRLLRLLRRLRRLRLLLRRRLRLRLRLRLLRRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLLRRLRLRLLLRLLRLRRRRLRLRLRLRLRLRLLRLLRRRLRLRLRLRLRLRLRLLRRLLLRRRLLRRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLLRRLRLLLRRRLRLRL...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #8:
score: 0
Wrong Answer
time: 2ms
memory: 3808kb
input:
200000 200000 LLRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLLRRLRLRLRLLLLRLRRRLRRLRLRLRLLLLRRLRRRLLRRLLRRLRLRLRLRLRLRLLRLRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLLRLRRLRLRLRLRLLRLRLRRLRLLLRRRLRLRLRLRLRLRLRLLRRLRLLLRRLRLRRLRLRLLRRLRLLRRLLRRLRLRLRLRLRLRLLLRRRLLRRLLRRLRLRLRLRLRLRLRLRLRLRLLR...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #9:
score: 0
Wrong Answer
time: 2ms
memory: 3784kb
input:
200000 200000 LLLRRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLLRRLRLRLLRRLLRLRRLLLRRLRRLRLRLLRRLRLRLRLRLRLLRLRRLLRLRRLRLLRRLRLRLRLRLRLRLRLRLLLRRLRRLRLRLRLLLLRRRRLRLRLRLRLRLRLRLRLLRRLLRRLRLLRRLRLLLRRRLLRRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLLRRLRLRLLLRRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRLRRLLLRRRLRLRLLRRLRLRLRLRL...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #10:
score: 0
Wrong Answer
time: 2ms
memory: 3784kb
input:
200000 200000 LLRLLRRLRLLRRLRLLRRLRLLRRLRLLRRLRLRLRLLRRLRLRLRLRLRLLRLRRLRLLRRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLLRRLRLRLRLRLLLRLRLRLRRRLRLRLRLRLRLRLLRRLRLLRLRLRRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLLRLRRLRLRLRLRLRLRLLLRLRRRLRLRLRL...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #11:
score: 0
Wrong Answer
time: 2ms
memory: 3760kb
input:
200000 200000 LLRLRLLRRLRLRLLRRLRLLLRRLRLRRLRLRLRLRLRLRLRLRLLRLRLLRLRRLRRLRLRLRLRLRLLRRLLRRLRLRLRLLRRLLRLRRLRLRLRLRLRLRLRLLRRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLLRRLRLLRRLLRRLRLRLRLRLRLRLRLLRRLLRRLRLLRRLRLLRRLLRLRRLRLRLLLLRRRRLRLRLRLLLRRRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLLRRL...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 3792kb
input:
200000 200000 LLRLRLRLRLRLRLRLRLRLLRRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLLRLRRLRLRLRLRLRLRLLRRLRLRLRLLRRLRLLRRLLRRLRLLRRLRLRLRLRLRLRLRLRLLLRLRRRLRLRLRLRLLRLRRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLLRLRRLRLLLRRRLRLRLRLRLRLRLLRRLLRLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLLRLRRRLRLLRRL...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #13:
score: 0
Wrong Answer
time: 2ms
memory: 3856kb
input:
200000 200000 LLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLLRRLRLRLRLRLRLLRRLRLLRLRRLRLRLRLRLRLLRRLLRLRRLRLRLLRRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLLRRRLLLRRRLRLRLRLLRLRRLRLRLRLRLRLRLLLRRRLRLLLRRRLRLLRRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLLRRLRLLLLLRRRRRLRLRLRLLRRLRLRLRLLRLRRLLLRRRLRLRLLRRLRL...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #14:
score: 0
Wrong Answer
time: 2ms
memory: 3780kb
input:
200000 200000 LLLRRLRLRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLLRRLRLRLRLLLRRRLRLLRRLLRRLLLRRRLRLRLLLLLRRRRRLRLRLRLRLLRLRRLRLLLRRRLLRLRRLRLRLRLRLLRLLRRRLRLLRRLRLLLRRRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLLRRLLLRLRRRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRLRLRRLLRLRRLLRRLRLRL...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #15:
score: 0
Wrong Answer
time: 2ms
memory: 3836kb
input:
200000 200000 LLRLRLLRRLRLRLRLRLRLRLLRRLRLLRRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLLLRRRLRLRLRLRLRLRLRLRLRLLLRLRRRLRLRLRLRLRLLRRLLLLRLRRLRRRLRLRLLLRRLRRLRLRLRLRLRLRLRLRLLLLRRLLRRRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLLLRRRLLRRLRLRLRLLLRRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRL...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements
Test #16:
score: 0
Wrong Answer
time: 2ms
memory: 3772kb
input:
200000 200000 LLRLRLLRRLRLRLRLRLRLRLLRRLRLRLLRRLRLRLLRRLRLLRRLRLLRRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLLRLRRLLLRRRLRLRLRLLLRRRLRLRLRLLLRRRLRLLRRLLLRLRLLRRRRLRLRLLRRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLLRRLRLLRRLRLLRRLRLRLRLRLRLRLRLRL...
output:
result:
wrong answer Answer contains longer sequence [length = 400000], but output contains 0 elements