oj.uz

Submission #304671

# Submission time Handle Problem Language Result Execution time Memory
304671 2020-09-21T17:09:27 Z oleh1421 Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 452900 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;
//        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=(pos+i)%n;
            if (p[nxt]<p[pos]){
                g[pos].push_back(nxt);
            }
        }
        for (int i=1;i<k;i++){
            int nxt=(pos-i+n)%n;
            if (p[nxt]<p[pos]){
                g[pos].push_back(nxt);
            }
        }

//        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] || can1[x][y]) return 1;
    if (can[y][x] || can1[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



*/

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:192:13: warning: unused variable 'nxt1' [-Wunused-variable]
  192 |         int nxt1=get_pos(n,pos,(pos+k-1)%n);
      |             ^~~~
plants.cpp:193:13: warning: unused variable 'nxt2' [-Wunused-variable]
  193 |         int nxt2=get_pos(n,(pos-k+1+n)%n,pos);
      |             ^~~~

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 14592 KB Output is correct
5 Correct 9 ms 14592 KB Output is correct
6 Correct 77 ms 17528 KB Output is correct
7 Runtime error 227 ms 127480 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 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 10 ms 15360 KB Output is correct
6 Correct 250 ms 28280 KB Output is correct
7 Execution timed out 4062 ms 116596 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 14464 KB Output is correct
4 Correct 9 ms 14464 KB Output is correct
5 Correct 10 ms 15360 KB Output is correct
6 Correct 250 ms 28280 KB Output is correct
7 Execution timed out 4062 ms 116596 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 121 ms 35536 KB Output is correct
4 Runtime error 1442 ms 245240 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 10 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 9 ms 14720 KB Output is correct
6 Correct 11 ms 15360 KB Output is correct
7 Correct 26 ms 17664 KB Output is correct
8 Correct 31 ms 17920 KB Output is correct
9 Correct 27 ms 17664 KB Output is correct
10 Correct 31 ms 17920 KB Output is correct
11 Correct 27 ms 17656 KB Output is correct
12 Correct 28 ms 17784 KB Output is correct
13 Correct 36 ms 18168 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 14592 KB Output is correct
5 Correct 55 ms 24184 KB Output is correct
6 Runtime error 1936 ms 452900 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 14592 KB Output is correct
5 Correct 9 ms 14592 KB Output is correct
6 Correct 77 ms 17528 KB Output is correct
7 Runtime error 227 ms 127480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -