oj.uz

Submission #304489

# Submission time Handle Problem Language Result Execution time Memory
304489 2020-09-21T12:18:48 Z oleh1421 Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 192888 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=A.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;
    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<r.size();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);
        }
        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++){
        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

*/

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i=0;i<r.size();i++) a[i]=r[i];
      |                  ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 6 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 64 ms 11256 KB Execution failed because the return code was nonzero
8 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 7 ms 7936 KB Output is correct
6 Correct 489 ms 21240 KB Output is correct
7 Execution timed out 4106 ms 192888 KB Time limit exceeded
8 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 7 ms 7936 KB Output is correct
6 Correct 489 ms 21240 KB Output is correct
7 Execution timed out 4106 ms 192888 KB Time limit exceeded
8 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 Runtime error 5 ms 7424 KB Execution failed because the return code was nonzero
3 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 7552 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 6 ms 7424 KB Output is correct
5 Runtime error 5 ms 7424 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 Runtime error 5 ms 7424 KB Execution failed because the return code was nonzero
5 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 6 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 64 ms 11256 KB Execution failed because the return code was nonzero
8 Halted 0 ms 0 KB -