oj.uz

답안 #304672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
304672 2020-09-21T17:10:19 Z oleh1421 식물 비교 (IOI20_plants) C++17
11 / 100
 4000 ms 465904 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]){
                rg[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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 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 10 ms 14592 KB Output is correct
6 Correct 70 ms 17472 KB Output is correct
7 Runtime error 231 ms 127608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 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 14464 KB Output is correct
5 Correct 10 ms 15360 KB Output is correct
6 Correct 290 ms 29304 KB Output is correct
7 Execution timed out 4065 ms 124024 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 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 14464 KB Output is correct
5 Correct 10 ms 15360 KB Output is correct
6 Correct 290 ms 29304 KB Output is correct
7 Execution timed out 4065 ms 124024 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 9 ms 14592 KB Output is correct
3 Correct 117 ms 36184 KB Output is correct
4 Runtime error 1584 ms 261680 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

# 결과 실행 시간 메모리 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 10 ms 14464 KB Output is correct
5 Correct 9 ms 14720 KB Output is correct
6 Correct 12 ms 15360 KB Output is correct
7 Correct 25 ms 17664 KB Output is correct
8 Correct 31 ms 17912 KB Output is correct
9 Correct 26 ms 17656 KB Output is correct
10 Correct 31 ms 17920 KB Output is correct
11 Correct 26 ms 17664 KB Output is correct
12 Correct 27 ms 17652 KB Output is correct
13 Correct 38 ms 18296 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 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 65 ms 24952 KB Output is correct
6 Runtime error 1861 ms 465904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 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 10 ms 14592 KB Output is correct
6 Correct 70 ms 17472 KB Output is correct
7 Runtime error 231 ms 127608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -