oj.uz

Submission #304682

# Submission time Handle Problem Language Result Execution time Memory
304682 2020-09-21T17:25:45 Z oleh1421 Comparing Plants (IOI20_plants) C++17
100 / 100
 2023 ms 171640 KB 
#define SYS
#ifdef SYS
#include "plants.h"
#endif // SYS


#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=400010;
struct node{
    int mx,l,r,best;
};
node t[N*4];
int w[N*4];
int a[N];
int p[N];
int nn,kk;
node Merge(node A,node B){
    if (A.mx>B.mx) {
        return A;
    }
    if (A.mx<B.mx) {
        return B;
    }
    node C;
    C.mx=A.mx;
    C.l=A.l;
    C.r=B.r;
    if (A.best!=-1) C.best=A.best;
    else if (B.best!=-1) C.best=B.best;
    else if (B.l>=A.r+kk) C.best=B.l;
    else C.best=-1;
    return C;
}
void build(int v,int l,int r){
    if (l>r) return;
    w[v]=0;
    t[v].best=-1;
    if (l==r){
        t[v].mx=a[l];
        t[v].l=t[v].r=l;
        t[v].best=-1;
        return;
    }
    int m=(l+r)/2;
    build(v+v,l,m);
    build(v+v+1,m+1,r);
    t[v]=Merge(t[v+v],t[v+v+1]);
}
void push(int v){
    t[v+v].mx+=w[v];
    t[v+v+1].mx+=w[v];
    w[v+v]+=w[v];
    w[v+v+1]+=w[v];
    w[v]=0;
}
void upd(int v,int l,int r,int L,int R,int x){
    if (l>R || r<L) return;
    if (l>=L && r<=R){
        t[v].mx+=x;
        w[v]+=x;
        return;
    }
    push(v);
    int m=(l+r)/2;
    upd(v+v,l,m,L,R,x);
    upd(v+v+1,m+1,r,L,R,x);
    t[v]=Merge(t[v+v],t[v+v+1]);
}
void add(int n,int l,int r,int x){
    if (l<=r){
        upd(1,0,n-1,l,r,x);
    } else {
        upd(1,0,n-1,l,n-1,x);
        upd(1,0,n-1,0,r,x);
    }
}
int go1[N];
int go2[N];
int rp[N];
pair<int,int>t1[N*4];
void upd1(int v,int l,int r,int pos,int x){
    if (l==r){
        t1[v]={x,l};
        return;
    }
    int m=(l+r)/2;
    if (pos<=m) upd1(v+v,l,m,pos,x);
    else upd1(v+v+1,m+1,r,pos,x);
    t1[v]=max(t1[v+v],t1[v+v+1]);
}
pair<int,int> get1(int v,int l,int r,int L,int R){
    if (l>R || r<L) return {-1,-1};
    if (l>=L && r<=R) return t1[v];
    int m=(l+r)/2;
    return max(get1(v+v,l,m,L,R),get1(v+v+1,m+1,r,L,R));
}
int get_pos(int n,int l,int r){
    pair<int,int>cur;
    if (l<=r){
        cur=get1(1,0,n-1,l,r);
    } else {
        cur=max(get1(1,0,n-1,0,r),get1(1,0,n-1,l,n-1));
    }
    if (cur.first<=0) return -1;
    return cur.second;
}

vector<int>g[N];
vector<int>rg[N];

int go_1(int x){
    if (go1[x]==x) return x;
    return go1[x]=go_1(go1[x]);
}
int go_2(int x){
    if (go2[x]==x) return x;
    return go2[x]=go_2(go2[x]);
}
bool used[N];
void dfs(int v){
    used[v]=true;
    for (int to:g[v]){
        if (!used[to]) dfs(to);
    }
}
bool used1[N];
void dfs1(int v){
    used1[v]=true;
    for (int to:rg[v]){
        if (!used1[to]) dfs1(to);
    }
}
const int L=25;
int up1[N][L];
ll skip1[N][L];
int up2[N][L];
ll skip2[N][L];
bool can1(int x,int y){
    if (p[x]<p[y]) return 0;
//    cout<<x<<" "<<y<<endl;
    int last=x;
    ll skip=0;
    for (int i=L-1;i>=0;i--){
        if (p[up1[x][i]]>=p[y]) skip+=skip1[x][i],x=up1[x][i];
    }
    if (skip>=nn) return 1;
//    cout<<x<<" "<<y<<endl<<endl;
    if (last<y){
        return (x>=y || x<last);
    } else {
//        last>y<=x
        return (x>=y && x<last);
    }

}
bool can2(int x,int y){
    if (p[x]<p[y]) return 0;
    int last=x;
    ll skip=0;
    for (int i=L-1;i>=0;i--){
        if (p[up2[x][i]]>=p[y]) skip+=skip2[x][i],x=up2[x][i];
    }
    if (skip>=nn) return 1;
    if (last>y){
        return (x<=y || x>last);
    } else {
        return (x<=y && x>last);
    }

}
bool can(int x,int y){
    return (can1(x,y)|can2(x,y));
}
void init(int k, std::vector<int> r) {
    int n=r.size();
    nn=n;
    kk=k;

    for (int &i:r){
        i=k-i-1;
    }
    for (int i=0;i<n;i++) a[i]=r[i];
    build(1,0,n-1);
    for (int cur=n;cur>=1;cur--){
        if (t[1].mx!=k-1) exit(1);
        int pos=(t[1].best==-1 ? t[1].l : t[1].best);
        p[pos]=cur;
        rp[cur]=pos;
//        cout<<pos<<endl;
        add(n,(pos-k+1+n)%n,pos,1);
        add(n,pos,pos,-n*3);
    }
    for (int cur=1;cur<=n;cur++){
        int pos=rp[cur];
        int nxt1=get_pos(n,pos,(pos+k-1)%n);
        int nxt2=get_pos(n,(pos-k+1+n)%n,pos);

        if (nxt1!=-1) g[pos].push_back(nxt1),rg[nxt1].push_back(pos);
        else nxt1=pos;
        if (nxt2!=-1) g[pos].push_back(nxt2),rg[nxt2].push_back(pos);
        else nxt2=pos;
        go1[pos]=nxt1;
        go2[pos]=nxt2;
        upd1(1,0,n-1,pos,cur);
        skip1[pos][0]=(go1[pos]-pos+n)%n;
        up1[pos][0]=go1[pos];
        skip2[pos][0]=(pos-go2[pos]+n)%n;
        up2[pos][0]=go2[pos];
    }
//    for (int i=0;i<n;i++){
//        cout<<i<<" "<<go1[i]<<" "<<go2[i]<<" "<<p[i]<<endl;
//    }
    for (int i=1;i<L;i++){
        for (int j=0;j<n;j++){
            skip1[j][i]=skip1[j][i-1]+skip1[up1[j][i-1]][i-1];
            up1[j][i]=up1[up1[j][i-1]][i-1];
            skip2[j][i]=skip2[j][i-1]+skip2[up2[j][i-1]][i-1];
            up2[j][i]=up2[up2[j][i-1]][i-1];
        }
    }


	return;
}

int compare_plants(int x, int y) {
    if (can(x,y)) return 1;
    if (can(y,x)) return -1;
//    exit(1);
	return 0;
}

#ifndef SYS
#include <cstdio>
#include <cassert>
#include <vector>

static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
	assert(scanf("%d%d%d", &n, &k, &q) == 3);
	r.resize(n);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		int value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	return 0;
}
#endif

/*
4 3 2
0 1 1 2
0 2
1 2



*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19200 KB Output is correct
2 Correct 13 ms 19200 KB Output is correct
3 Correct 13 ms 19200 KB Output is correct
4 Correct 13 ms 19200 KB Output is correct
5 Correct 14 ms 19200 KB Output is correct
6 Correct 118 ms 22008 KB Output is correct
7 Correct 234 ms 37368 KB Output is correct
8 Correct 820 ms 170872 KB Output is correct
9 Correct 845 ms 171256 KB Output is correct
10 Correct 882 ms 171368 KB Output is correct
11 Correct 919 ms 171312 KB Output is correct
12 Correct 914 ms 171260 KB Output is correct
13 Correct 992 ms 171312 KB Output is correct
14 Correct 1014 ms 171384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19200 KB Output is correct
2 Correct 13 ms 19200 KB Output is correct
3 Correct 13 ms 19200 KB Output is correct
4 Correct 13 ms 19200 KB Output is correct
5 Correct 14 ms 19328 KB Output is correct
6 Correct 19 ms 19968 KB Output is correct
7 Correct 190 ms 25848 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 19 ms 19968 KB Output is correct
10 Correct 189 ms 25848 KB Output is correct
11 Correct 156 ms 25720 KB Output is correct
12 Correct 160 ms 25976 KB Output is correct
13 Correct 190 ms 25848 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19200 KB Output is correct
2 Correct 13 ms 19200 KB Output is correct
3 Correct 13 ms 19200 KB Output is correct
4 Correct 13 ms 19200 KB Output is correct
5 Correct 14 ms 19328 KB Output is correct
6 Correct 19 ms 19968 KB Output is correct
7 Correct 190 ms 25848 KB Output is correct
8 Correct 16 ms 19328 KB Output is correct
9 Correct 19 ms 19968 KB Output is correct
10 Correct 189 ms 25848 KB Output is correct
11 Correct 156 ms 25720 KB Output is correct
12 Correct 160 ms 25976 KB Output is correct
13 Correct 190 ms 25848 KB Output is correct
14 Correct 357 ms 37368 KB Output is correct
15 Correct 2007 ms 171512 KB Output is correct
16 Correct 384 ms 37368 KB Output is correct
17 Correct 2023 ms 171384 KB Output is correct
18 Correct 1169 ms 171384 KB Output is correct
19 Correct 1209 ms 171384 KB Output is correct
20 Correct 1947 ms 171384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19200 KB Output is correct
2 Correct 13 ms 19200 KB Output is correct
3 Correct 169 ms 23544 KB Output is correct
4 Correct 1170 ms 171512 KB Output is correct
5 Correct 1179 ms 171640 KB Output is correct
6 Correct 1462 ms 171352 KB Output is correct
7 Correct 1756 ms 171464 KB Output is correct
8 Correct 1992 ms 171356 KB Output is correct
9 Correct 1018 ms 171352 KB Output is correct
10 Correct 1152 ms 171256 KB Output is correct
11 Correct 1027 ms 171256 KB Output is correct
12 Correct 1086 ms 171256 KB Output is correct
13 Correct 1204 ms 171296 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19200 KB Output is correct
2 Correct 15 ms 19200 KB Output is correct
3 Correct 13 ms 19200 KB Output is correct
4 Correct 14 ms 19200 KB Output is correct
5 Correct 18 ms 19200 KB Output is correct
6 Correct 16 ms 19304 KB Output is correct
7 Correct 36 ms 20088 KB Output is correct
8 Correct 37 ms 20088 KB Output is correct
9 Correct 49 ms 20088 KB Output is correct
10 Correct 44 ms 20088 KB Output is correct
11 Correct 37 ms 20088 KB Output is correct
12 Correct 39 ms 20008 KB Output is correct
13 Correct 39 ms 20088 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19200 KB Output is correct
2 Correct 18 ms 19200 KB Output is correct
3 Correct 12 ms 19144 KB Output is correct
4 Correct 18 ms 19200 KB Output is correct
5 Correct 15 ms 19968 KB Output is correct
6 Correct 1006 ms 171384 KB Output is correct
7 Correct 1366 ms 171448 KB Output is correct
8 Correct 1511 ms 171392 KB Output is correct
9 Correct 1776 ms 171384 KB Output is correct
10 Correct 954 ms 171308 KB Output is correct
11 Correct 1231 ms 171564 KB Output is correct
12 Correct 950 ms 171516 KB Output is correct
13 Correct 1043 ms 171384 KB Output is correct
14 Correct 1259 ms 171512 KB Output is correct
15 Correct 1554 ms 171384 KB Output is correct
16 Correct 931 ms 171384 KB Output is correct
17 Correct 963 ms 171640 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19200 KB Output is correct
2 Correct 13 ms 19200 KB Output is correct
3 Correct 13 ms 19200 KB Output is correct
4 Correct 13 ms 19200 KB Output is correct
5 Correct 14 ms 19200 KB Output is correct
6 Correct 118 ms 22008 KB Output is correct
7 Correct 234 ms 37368 KB Output is correct
8 Correct 820 ms 170872 KB Output is correct
9 Correct 845 ms 171256 KB Output is correct
10 Correct 882 ms 171368 KB Output is correct
11 Correct 919 ms 171312 KB Output is correct
12 Correct 914 ms 171260 KB Output is correct
13 Correct 992 ms 171312 KB Output is correct
14 Correct 1014 ms 171384 KB Output is correct
15 Correct 13 ms 19200 KB Output is correct
16 Correct 13 ms 19200 KB Output is correct
17 Correct 13 ms 19200 KB Output is correct
18 Correct 13 ms 19200 KB Output is correct
19 Correct 14 ms 19328 KB Output is correct
20 Correct 19 ms 19968 KB Output is correct
21 Correct 190 ms 25848 KB Output is correct
22 Correct 16 ms 19328 KB Output is correct
23 Correct 19 ms 19968 KB Output is correct
24 Correct 189 ms 25848 KB Output is correct
25 Correct 156 ms 25720 KB Output is correct
26 Correct 160 ms 25976 KB Output is correct
27 Correct 190 ms 25848 KB Output is correct
28 Correct 357 ms 37368 KB Output is correct
29 Correct 2007 ms 171512 KB Output is correct
30 Correct 384 ms 37368 KB Output is correct
31 Correct 2023 ms 171384 KB Output is correct
32 Correct 1169 ms 171384 KB Output is correct
33 Correct 1209 ms 171384 KB Output is correct
34 Correct 1947 ms 171384 KB Output is correct
35 Correct 14 ms 19200 KB Output is correct
36 Correct 13 ms 19200 KB Output is correct
37 Correct 169 ms 23544 KB Output is correct
38 Correct 1170 ms 171512 KB Output is correct
39 Correct 1179 ms 171640 KB Output is correct
40 Correct 1462 ms 171352 KB Output is correct
41 Correct 1756 ms 171464 KB Output is correct
42 Correct 1992 ms 171356 KB Output is correct
43 Correct 1018 ms 171352 KB Output is correct
44 Correct 1152 ms 171256 KB Output is correct
45 Correct 1027 ms 171256 KB Output is correct
46 Correct 1086 ms 171256 KB Output is correct
47 Correct 1204 ms 171296 KB Output is correct
48 Correct 14 ms 19200 KB Output is correct
49 Correct 15 ms 19200 KB Output is correct
50 Correct 13 ms 19200 KB Output is correct
51 Correct 14 ms 19200 KB Output is correct
52 Correct 18 ms 19200 KB Output is correct
53 Correct 16 ms 19304 KB Output is correct
54 Correct 36 ms 20088 KB Output is correct
55 Correct 37 ms 20088 KB Output is correct
56 Correct 49 ms 20088 KB Output is correct
57 Correct 44 ms 20088 KB Output is correct
58 Correct 37 ms 20088 KB Output is correct
59 Correct 39 ms 20008 KB Output is correct
60 Correct 39 ms 20088 KB Output is correct
61 Correct 136 ms 23416 KB Output is correct
62 Correct 231 ms 37240 KB Output is correct
63 Correct 896 ms 170812 KB Output is correct
64 Correct 1000 ms 171512 KB Output is correct
65 Correct 1357 ms 171512 KB Output is correct
66 Correct 1662 ms 171512 KB Output is correct
67 Correct 2005 ms 171384 KB Output is correct
68 Correct 977 ms 171436 KB Output is correct
69 Correct 1396 ms 171384 KB Output is correct
70 Correct 1006 ms 171620 KB Output is correct
71 Correct 1104 ms 171384 KB Output is correct
72 Correct 1436 ms 171388 KB Output is correct
73 Correct 1694 ms 171384 KB Output is correct
74 Correct 887 ms 171000 KB Output is correct
75 Correct 1033 ms 171512 KB Output is correct