oj.uz

Submission #304681

# Submission time Handle Problem Language Result Execution time Memory
304681 2020-09-21T17:22:59 Z oleh1421 Comparing Plants (IOI20_plants) C++17
75 / 100
 1988 ms 171672 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;
    int 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;
    int 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 13 ms 19200 KB Output is correct
6 Correct 116 ms 22012 KB Output is correct
7 Correct 247 ms 37368 KB Output is correct
8 Correct 814 ms 170872 KB Output is correct
9 Correct 863 ms 171296 KB Output is correct
10 Correct 858 ms 171256 KB Output is correct
11 Correct 898 ms 171384 KB Output is correct
12 Correct 907 ms 171256 KB Output is correct
13 Correct 971 ms 171256 KB Output is correct
14 Correct 988 ms 171308 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19328 KB Output is correct
2 Correct 14 ms 19200 KB Output is correct
3 Correct 14 ms 19200 KB Output is correct
4 Correct 13 ms 19200 KB Output is correct
5 Correct 15 ms 19200 KB Output is correct
6 Correct 19 ms 19968 KB Output is correct
7 Correct 187 ms 25848 KB Output is correct
8 Correct 20 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 160 ms 25720 KB Output is correct
12 Correct 163 ms 25976 KB Output is correct
13 Correct 192 ms 25848 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19328 KB Output is correct
2 Correct 14 ms 19200 KB Output is correct
3 Correct 14 ms 19200 KB Output is correct
4 Correct 13 ms 19200 KB Output is correct
5 Correct 15 ms 19200 KB Output is correct
6 Correct 19 ms 19968 KB Output is correct
7 Correct 187 ms 25848 KB Output is correct
8 Correct 20 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 160 ms 25720 KB Output is correct
12 Correct 163 ms 25976 KB Output is correct
13 Correct 192 ms 25848 KB Output is correct
14 Correct 369 ms 37496 KB Output is correct
15 Correct 1976 ms 171576 KB Output is correct
16 Correct 386 ms 37368 KB Output is correct
17 Correct 1972 ms 171640 KB Output is correct
18 Correct 1151 ms 171384 KB Output is correct
19 Correct 1164 ms 171256 KB Output is correct
20 Correct 1898 ms 171444 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19200 KB Output is correct
2 Correct 16 ms 19200 KB Output is correct
3 Correct 141 ms 23544 KB Output is correct
4 Correct 1111 ms 171568 KB Output is correct
5 Correct 1162 ms 171516 KB Output is correct
6 Correct 1468 ms 171512 KB Output is correct
7 Correct 1708 ms 171512 KB Output is correct
8 Correct 1980 ms 171468 KB Output is correct
9 Correct 974 ms 171384 KB Output is correct
10 Correct 1068 ms 171404 KB Output is correct
11 Correct 973 ms 171408 KB Output is correct
12 Correct 1036 ms 171512 KB Output is correct
13 Correct 1141 ms 171512 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19200 KB Output is correct
2 Correct 14 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 13 ms 19204 KB Output is correct
6 Correct 16 ms 19328 KB Output is correct
7 Correct 37 ms 20088 KB Output is correct
8 Correct 38 ms 20088 KB Output is correct
9 Correct 39 ms 20088 KB Output is correct
10 Correct 38 ms 20092 KB Output is correct
11 Correct 37 ms 20088 KB Output is correct
12 Correct 39 ms 20088 KB Output is correct
13 Correct 42 ms 20088 KB Output is correct

Subtask #6
15.0 / 15.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 16 ms 19968 KB Output is correct
6 Correct 970 ms 171512 KB Output is correct
7 Correct 1288 ms 171572 KB Output is correct
8 Correct 1456 ms 171384 KB Output is correct
9 Correct 1717 ms 171568 KB Output is correct
10 Correct 909 ms 171512 KB Output is correct
11 Correct 1228 ms 171640 KB Output is correct
12 Correct 920 ms 171304 KB Output is correct
13 Correct 1046 ms 171640 KB Output is correct
14 Correct 1277 ms 171552 KB Output is correct
15 Correct 1543 ms 171640 KB Output is correct
16 Correct 915 ms 171192 KB Output is correct
17 Correct 969 ms 171640 KB Output is correct

Subtask #7
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 13 ms 19200 KB Output is correct
6 Correct 116 ms 22012 KB Output is correct
7 Correct 247 ms 37368 KB Output is correct
8 Correct 814 ms 170872 KB Output is correct
9 Correct 863 ms 171296 KB Output is correct
10 Correct 858 ms 171256 KB Output is correct
11 Correct 898 ms 171384 KB Output is correct
12 Correct 907 ms 171256 KB Output is correct
13 Correct 971 ms 171256 KB Output is correct
14 Correct 988 ms 171308 KB Output is correct
15 Correct 13 ms 19328 KB Output is correct
16 Correct 14 ms 19200 KB Output is correct
17 Correct 14 ms 19200 KB Output is correct
18 Correct 13 ms 19200 KB Output is correct
19 Correct 15 ms 19200 KB Output is correct
20 Correct 19 ms 19968 KB Output is correct
21 Correct 187 ms 25848 KB Output is correct
22 Correct 20 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 160 ms 25720 KB Output is correct
26 Correct 163 ms 25976 KB Output is correct
27 Correct 192 ms 25848 KB Output is correct
28 Correct 369 ms 37496 KB Output is correct
29 Correct 1976 ms 171576 KB Output is correct
30 Correct 386 ms 37368 KB Output is correct
31 Correct 1972 ms 171640 KB Output is correct
32 Correct 1151 ms 171384 KB Output is correct
33 Correct 1164 ms 171256 KB Output is correct
34 Correct 1898 ms 171444 KB Output is correct
35 Correct 13 ms 19200 KB Output is correct
36 Correct 16 ms 19200 KB Output is correct
37 Correct 141 ms 23544 KB Output is correct
38 Correct 1111 ms 171568 KB Output is correct
39 Correct 1162 ms 171516 KB Output is correct
40 Correct 1468 ms 171512 KB Output is correct
41 Correct 1708 ms 171512 KB Output is correct
42 Correct 1980 ms 171468 KB Output is correct
43 Correct 974 ms 171384 KB Output is correct
44 Correct 1068 ms 171404 KB Output is correct
45 Correct 973 ms 171408 KB Output is correct
46 Correct 1036 ms 171512 KB Output is correct
47 Correct 1141 ms 171512 KB Output is correct
48 Correct 13 ms 19200 KB Output is correct
49 Correct 14 ms 19200 KB Output is correct
50 Correct 13 ms 19200 KB Output is correct
51 Correct 13 ms 19200 KB Output is correct
52 Correct 13 ms 19204 KB Output is correct
53 Correct 16 ms 19328 KB Output is correct
54 Correct 37 ms 20088 KB Output is correct
55 Correct 38 ms 20088 KB Output is correct
56 Correct 39 ms 20088 KB Output is correct
57 Correct 38 ms 20092 KB Output is correct
58 Correct 37 ms 20088 KB Output is correct
59 Correct 39 ms 20088 KB Output is correct
60 Correct 42 ms 20088 KB Output is correct
61 Correct 138 ms 23416 KB Output is correct
62 Correct 230 ms 37240 KB Output is correct
63 Correct 911 ms 170656 KB Output is correct
64 Correct 997 ms 171384 KB Output is correct
65 Correct 1361 ms 171640 KB Output is correct
66 Correct 1650 ms 171672 KB Output is correct
67 Incorrect 1988 ms 171664 KB Output isn't correct
68 Halted 0 ms 0 KB -