Submission #527953

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
527953	2022-02-18 20:34:11	AdamGS	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	556 ms	65540 KiB

snake_escaping

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
const int LIM=1<<20;
int T[LIM], ans[LIM], n, q;
pair<string,int>pyt[LIM];
void solve(int l, int r, int k, int a, int b) {
    if(l==r) {
        while(a<=b) {
            ans[pyt[a].nd]=T[l];
            ++a;
        }
        return;
    }
    int x=a;
    while(x<=b && pyt[x].st[k]=='0') ++x;
    if(x>a) solve(l, (l+r)/2, k+1, a, x-1);
    int y=x;
    while(y<=b && pyt[y].st[k]=='1') ++y;
    if(y>x) solve((l+r)/2+1, r, k+1, x, y-1);
    if(y<=b) {
        rep(i, (r-l+1)/2) T[l+i]+=T[(l+r)/2+1+i];
        solve(l, (l+r)/2, k+1, y, b);
        rep(i, (r-l+1)/2) T[l+i]-=T[(l+r)/2+1+i];
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 0 / 25