oj.uz

Submission #304515

# Submission time Handle Problem Language Result Execution time Memory
304515 2020-09-21T12:51:53 Z oleh1421 Comparing Plants (IOI20_plants) C++17
25 / 100
 3480 ms 116472 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);
    }
}
vector<int>g[N];
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);
        }
    }
}
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;
//        cout<<pos<<endl;
//        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);
//        }
        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);
        if (nxt2!=-1) g[i].push_back(nxt2);
    }
    for (int i=0;i<n;i++){
        dfs(i,i);
    }
	return;
}

int compare_plants(int x, int y) {
    if (can[x][y]) return 1;
    if (can[y][x]) return -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 2 2
0 1 0 1
0 3
1 3

*/

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 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7424 KB Output is correct
6 Correct 67 ms 10360 KB Output is correct
7 Runtime error 143 ms 65912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Output is correct
2 Correct 5 ms 7456 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 7808 KB Output is correct
6 Correct 29 ms 12544 KB Output is correct
7 Correct 679 ms 35448 KB Output is correct
8 Correct 8 ms 7936 KB Output is correct
9 Correct 29 ms 12416 KB Output is correct
10 Correct 638 ms 35564 KB Output is correct
11 Correct 327 ms 35320 KB Output is correct
12 Correct 325 ms 35216 KB Output is correct
13 Correct 726 ms 35576 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Output is correct
2 Correct 5 ms 7456 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 7808 KB Output is correct
6 Correct 29 ms 12544 KB Output is correct
7 Correct 679 ms 35448 KB Output is correct
8 Correct 8 ms 7936 KB Output is correct
9 Correct 29 ms 12416 KB Output is correct
10 Correct 638 ms 35564 KB Output is correct
11 Correct 327 ms 35320 KB Output is correct
12 Correct 325 ms 35216 KB Output is correct
13 Correct 726 ms 35576 KB Output is correct
14 Runtime error 3480 ms 74944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 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 97 ms 20092 KB Output is correct
4 Runtime error 601 ms 116472 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 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 7552 KB Output is correct
6 Correct 7 ms 7808 KB Output is correct
7 Correct 21 ms 9344 KB Output is correct
8 Correct 22 ms 9336 KB Output is correct
9 Correct 21 ms 9344 KB Output is correct
10 Correct 22 ms 9340 KB Output is correct
11 Correct 21 ms 9344 KB Output is correct
12 Correct 22 ms 9340 KB Output is correct
13 Correct 23 ms 9344 KB Output is correct

Subtask #6
0 / 15.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 18 ms 12416 KB Output is correct
6 Runtime error 878 ms 108920 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 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 5 ms 7424 KB Output is correct
6 Correct 67 ms 10360 KB Output is correct
7 Runtime error 143 ms 65912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -