oj.uz

Submission #304547

# Submission time Handle Problem Language Result Execution time Memory
304547 2020-09-21T13:29:39 Z oleh1421 Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 47212 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 L[N];
int R[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);
    }
}
void init(int k, std::vector<int> r) {
    int n=r.size();
    nn=n;
    kk=k;
    for (int i=0;i<n;i++){
        L[i]=R[i]=-1;
    }
    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 i=0;i<n;i++){
        int nxt1=-1;
        for (int j=1;j<k;j++){
            int cur=(i+j)%n;
            if (p[cur]<p[i] && (nxt1==-1 || p[nxt1]<p[cur])) nxt1=cur;
        }
        int nxt2=-1;
        for (int j=1;j<k;j++){
            int cur=(i-j+n)%n;
            if (p[cur]<p[i] && (nxt2==-1 || p[nxt2]<p[cur])) nxt2=cur;
        }
        if (nxt1!=-1) g[i].push_back(nxt1),rg[nxt1].push_back(i);
        else nxt1=i;
        if (nxt2!=-1) g[i].push_back(nxt2),rg[nxt2].push_back(i);
        else nxt2=i;
        go1[i]=nxt1;
        go2[i]=nxt2;
//        int pos=rp[cur];
//        int nxt1=get_pos(n,pos,(pos+k-1)%n);
//        if (nxt1==-1) nxt1=pos;
//        go1[pos]=nxt1;
//        int nxt2=get_pos(n,(pos-k+1+n)%n,pos);
//        if (nxt2==-1) nxt2=pos;
//        go2[pos]=nxt2;
//        upd1(1,0,n-1,pos,cur);
//        if (nxt1!=pos) {
//            g[pos].push_back(nxt1);
////            cout<<pos<<" "<<nxt1<<endl;
//        }
//        if (nxt2!=pos) {
//            g[pos].push_back(nxt2);
////            cout<<pos<<" "<<nxt2<<endl;
//        }
    }
    dfs(0);
    dfs1(0);

	return;
}

int compare_plants(int x, int y) {
    if (x) exit(1);
    if (used[y]) return 1;
    if (used1[y]) return -1;
    return 0;
//    int mult=1;
//    if (x>y){
//        swap(x,y);
//        mult=-1;
//    }
//
//    if (p[x]>p[y]){
//        if (go_1(x)>=y || go_1(x)<x) return mult;
//        if (go_2(x)<=y && go_2(x)>x) return mult;
//        return 0;
//    } else {
//        if (go_1(y)>=x && go_1(y)<y) return -mult;
//        if (go_2(y)<=x || go_2(y)>y) return -mult;
//        return -0;
//
//    }
	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 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Runtime error 10 ms 14464 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Runtime error 10 ms 14464 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Runtime error 10 ms 14464 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 14464 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Runtime error 10 ms 14464 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14464 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 13 ms 14592 KB Output is correct
6 Correct 662 ms 46968 KB Output is correct
7 Correct 3343 ms 47212 KB Output is correct
8 Execution timed out 4067 ms 34772 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Runtime error 10 ms 14464 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -