oj.uz

Submission #304536

# Submission time Handle Problem Language Result Execution time Memory
304536 2020-09-21T13:22:29 Z oleh1421 Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 2097156 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];
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]);
}
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),nxt1=i;
        if (nxt2!=-1) g[i].push_back(nxt2),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;
//        }
    }

	return;
}

int compare_plants(int x, int y) {
    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 mult;
    } else {
        if (go_1(y)>=x && go_1(y)<y) return -mult;
        if (go_2(y)<=x || go_2(y)>y) return -mult;
        return -mult;

    }
	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 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Runtime error 1478 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 19 ms 7552 KB Output is correct
7 Correct 399 ms 11128 KB Output is correct
8 Correct 7 ms 7552 KB Output is correct
9 Correct 19 ms 7552 KB Output is correct
10 Correct 366 ms 11000 KB Output is correct
11 Correct 220 ms 10872 KB Output is correct
12 Runtime error 1507 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 19 ms 7552 KB Output is correct
7 Correct 399 ms 11128 KB Output is correct
8 Correct 7 ms 7552 KB Output is correct
9 Correct 19 ms 7552 KB Output is correct
10 Correct 366 ms 11000 KB Output is correct
11 Correct 220 ms 10872 KB Output is correct
12 Runtime error 1507 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 81 ms 10488 KB Output is correct
4 Correct 348 ms 33360 KB Output is correct
5 Correct 629 ms 33528 KB Output is correct
6 Correct 3142 ms 33472 KB Output is correct
7 Execution timed out 4059 ms 26576 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Runtime error 1361 ms 2097152 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7456 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Runtime error 1341 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Runtime error 1478 ms 2097156 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -