oj.uz

Submission #304669

# Submission time Handle Problem Language Result Execution time Memory
304669 2020-09-21T17:07:20 Z oleh1421 Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 349856 KB 
#define SYS
#ifdef SYS
#include "plants.h"
#endif // SYS


#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=300010;
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 can[5010][5010];
void dfs(int v,int root){
    can[root][v]=true;
    for (int to:g[v]){
        if (!can[root][to]) dfs(to,root);
    }
}
bool can1[5010][5010];
void dfs1(int v,int root){
    can1[root][v]=true;
    for (int to:rg[v]){
        if (!can1[root][to]) dfs1(to,root);
    }
}
const int L=20;
int up1[N][L];
int up2[N][L];
//bool can1(int x,int y){
//    if (p[x]<p[y]) return 0;
////    cout<<x<<" "<<y<<endl;
//    int last=x;
//    for (int i=L-1;i>=0;i--){
//        if (p[up1[x][i]]>=p[y]) x=up1[x][i];
//    }
////    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;
//    for (int i=L-1;i>=0;i--){
//        if (p[up2[x][i]]>=p[y]) x=up2[x][i];
//    }
//    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;
        for (int i=1;i<k;i++){
            int nxt=(pos-i+n)%n;
            if (p[nxt]>p[pos]) g[nxt].push_back(pos);
            else g[pos].push_back(nxt);
        }
//        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);
//        for (int i=1;i<k;i++){
//            int nxt=(cur+i)%n;
//            if (p[nxt]<p[pos]){
//                g[pos].push_back(nxt);
//            }
//        }
//        for (int i=1;i<k;i++){
//            int nxt=(cur-i+n)%n;
//            if (p[nxt]<p[pos]){
//                g[pos].push_back(nxt);
//            } else {
//                g[nxt].push_back(pos);
//            }
//        }
//
////        if (nxt1!=-1) g[pos].push_back(nxt1);
////        else nxt1=pos;
////        if (nxt2!=-1) rg[pos].push_back(nxt2);
////        else nxt2=pos;
////        go1[pos]=nxt1;
////        go2[pos]=nxt2;
////        upd1(1,0,n-1,pos,cur);
////
////        up1[pos][0]=go1[pos];
////        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++){
//            up1[j][i]=up1[up1[j][i-1]][i-1];
//            up2[j][i]=up2[up2[j][i-1]][i-1];
//        }
//    }
    for (int i=0;i<n;i++){
        dfs(i,i);
//        dfs1(i,i);
    }

	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 9 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 9 ms 14464 KB Output is correct
6 Correct 75 ms 17528 KB Output is correct
7 Runtime error 160 ms 80376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 9 ms 14592 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 10 ms 14976 KB Output is correct
6 Correct 264 ms 24216 KB Output is correct
7 Execution timed out 4094 ms 115572 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 9 ms 14592 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 10 ms 14976 KB Output is correct
6 Correct 264 ms 24216 KB Output is correct
7 Execution timed out 4094 ms 115572 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14592 KB Output is correct
3 Correct 108 ms 27128 KB Output is correct
4 Runtime error 1578 ms 141688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 10 ms 14592 KB Output is correct
6 Correct 11 ms 14976 KB Output is correct
7 Correct 24 ms 16384 KB Output is correct
8 Correct 29 ms 16640 KB Output is correct
9 Correct 26 ms 16384 KB Output is correct
10 Correct 28 ms 16632 KB Output is correct
11 Correct 24 ms 16384 KB Output is correct
12 Correct 26 ms 16384 KB Output is correct
13 Correct 34 ms 16888 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 52 ms 19960 KB Output is correct
6 Runtime error 1974 ms 349856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Correct 9 ms 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 9 ms 14464 KB Output is correct
6 Correct 75 ms 17528 KB Output is correct
7 Runtime error 160 ms 80376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -