oj.uz

Submission #302607

# Submission time Handle Problem Language Result Execution time Memory
302607 2020-09-18T21:23:23 Z Dremix10 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 19448 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end();
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<","<<#y<<" = "<<"("<<x<<"-"<<y<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;

vector<int> arr,bigger;


vector<int> seg;
vector<int> laz;
vector<int> pou;

void join(int par, int x, int y){
    if(seg[x]<seg[y]){
        seg[par] = seg[x];
        pou[par] = pou[x];
    }
    else{
        seg[par] = seg[y];
        pou[par] = pou[y];
    }
}

void push(int par, int x, int y){
    seg[x] += laz[par];
    laz[x] += laz[par];
    seg[y] += laz[par];
    laz[y] += laz[par];
    laz[par] = 0;
}

void build(int s, int e, int idx){
    if(s==e){
        seg[idx] = 1e9;
        pou[idx] = s;
        return;
    }
    int mid = (s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);
    join(idx,idx*2,idx*2+1);
}

void update(int s, int e, int idx, int qs, int qe, int x){
    if(qs<=s && e<=qe){
        seg[idx] += x;
        laz[idx] += x;
        return;
    }
    if(s>qe || e<qs)return;
    int mid = (s+e)/2;
    push(idx,idx*2,idx*2+1);
    update(s,mid,idx*2,qs,qe,x);
    update(mid+1,e,idx*2+1,qs,qe,x);
    join(idx,idx*2,idx*2+1);
    //p2(s,e)
    //p2(seg[idx],pou[idx])
}


void init(int k, vector<int> r) {
	int n = r.size();
	arr.assign(n,0);
    bigger.assign(n,0);
    seg.assign((n+5)*4,0);
    laz.assign((n+5)*4,0);
    pou.assign((n+5)*4,0);
    int i,j;
    build(0,n-1,1);

    for(i=0;i<n;i++){
        if(r[i]==0){
            p(i)
            p2(i+k-1,n)
            if(i+1<n){
                update(0,n-1,1,i+1,min(n-1,i+k-1),1);
            }
            if(i+k-1>=n){
                p((i+k-1)%n)
                update(0,n-1,1,0,(i+k-1)%n,1);
            }
            update(0,n-1,1,i,i,-1e9);
        }
    }

    int curr = n;

    for(int t=0;t<n;t++){

        int x = pou[1];
        //p2(pou[1],seg[1])
        arr[x] = curr--;
        update(0,n-1,1,x,x,1e9);
        //pv(arr)
        //for(auto xx : s)
        //    cout<<xx.pos<<" ";
        //cout<<endl;
        //pv(bigger)
        //pv(r)
        //cout<<endl;
        if(x+1<n){
                update(0,n-1,1,x+1,min(n-1,x+k-1),-1);
            }
            if(x+k-1>=n){
                update(0,n-1,1,0,(x+k-1)%n,-1);
            }
        for(j=1;j<k;j++){
            //cout<<j<<" "<<k<<endl;



            int idx = x-j;
            if(idx<0)idx+=n;
            if(r[idx]>0){
                r[idx]--;
                if(r[idx]==0){
                    if(idx+1<n){
                        update(0,n-1,1,idx+1,min(n-1,idx+k-1),1);
                    }
                    if(idx+k-1>=n){
                        update(0,n-1,1,0,(idx+k-1)%n,1);
                    }
                    update(0,n-1,1,idx,idx,-1e9);
                }
            }
        }

        //pv(bigger)
        //pv(zer)
        //pv(r)

	}
    pv(arr)

}


int compare_plants(int x, int y) {
    if(arr[x]>arr[y])return 1;
    return -1;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 182 ms 3576 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 11 ms 512 KB Output is correct
10 Correct 180 ms 3576 KB Output is correct
11 Correct 192 ms 3448 KB Output is correct
12 Correct 135 ms 3704 KB Output is correct
13 Correct 197 ms 3580 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 182 ms 3576 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 11 ms 512 KB Output is correct
10 Correct 180 ms 3576 KB Output is correct
11 Correct 192 ms 3448 KB Output is correct
12 Correct 135 ms 3704 KB Output is correct
13 Correct 197 ms 3580 KB Output is correct
14 Correct 1129 ms 4728 KB Output is correct
15 Execution timed out 4027 ms 15380 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 108 ms 3448 KB Output is correct
4 Correct 3336 ms 19448 KB Output is correct
5 Correct 1921 ms 17528 KB Output is correct
6 Correct 2379 ms 16964 KB Output is correct
7 Execution timed out 4102 ms 15320 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -