oj.uz

Submission #343398

# Submission time Handle Problem Language Result Execution time Memory
343398 2021-01-03T22:07:21 Z MvC Comparing Plants (IOI20_plants) C++14
14 / 100
 4000 ms 23496 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=2e5+50;
const ll mod=1e9+7;
using namespace std;
int n,a[nmax],lzy[4*nmax],k;
pair<int,int>st[4*nmax];
pair<int,int> mrg(pair<int,int> x,pair<int,int> y)
{
    if(x.fr<y.fr)return x;
    else if(y.fr<x.fr)return y;
    return mkp(x.fr,min(x.sc,y.sc));
}
void build(int x,int l,int r,vector<int> v)
{
    if(l==r)
    {
        st[x]=mkp(v[l],l);
        return;
    }
    int mid=(l+r)/2;
    build(2*x,l,mid,v);
    build(2*x+1,mid+1,r,v);
    st[x]=mrg(st[2*x],st[2*x+1]);
}
void push(int nod,int l,int r)
{
    if(!lzy[nod])return;
    st[nod].fr+=lzy[nod];
    if(l!=r)
    {
    	lzy[nod*2]+=lzy[nod];
		lzy[nod*2+1]+=lzy[nod];
	}
    lzy[nod]=0;
}
void upd(int nod,int l,int r,int tl,int tr,int v)
{
    push(nod,l,r);
    if(tl<=l && r<=tr)
	{
        lzy[nod]+=v;
        push(nod,l,r);
        return;
    }
    int mid=(l+r)/2;
    if(tl<=mid)upd(nod*2,l,mid,tl,tr,v);
    if(mid<tr)upd(nod*2+1,mid+1,r,tl,tr,v);
    push(nod*2,l,mid);
	push(nod*2+1,mid+1,r);
    st[nod]=mrg(st[nod*2],st[nod*2+1]);
}
pair<int,int> qry(int nod,int l,int r,int tl,int tr)
{
    if(l>tr || r<tl)return mkp(inf,inf);
    push(nod,l,r);
    if(tl<=l && r<=tr)return st[nod];
    int mid=(l+r)/2;
    return mrg(qry(2*nod,l,mid,tl,tr),qry(2*nod+1,mid+1,r,tl,tr));
}
int solve(int x)
{
    if(x<k-1)
    {
        pair<int,int> y=qry(1,0,n-1,x-k+n+1,n-1);
        if(!y.fr)x=y.sc;
    }
    upd(1,0,n-1,x,x,2*n);
    if(x>=k-1)upd(1,0,n-1,x-k+1,x,-1);
    else
    {
        upd(1,0,n-1,0,x,-1);
        upd(1,0,n-1,x-k+n+1,n-1,-1);
    }
    return x;
}
void init(int K,vector<int> r)
{
    k=K;
    n=lun(r);
    build(1,0,n-1,r);
    for(int i=n-1;i>=0;i--)a[solve(qry(1,0,n-1,0,n-1).sc)]=i;
}
int compare_plants(int x,int y)
{
    if(a[x]>a[y])return 1;
    return -1;
}
/*int main()
{
    //freopen("sol.in","r",stdin);
    //freopen("sol.out","w",stdout);
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);

    return 0;
}*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 79 ms 5484 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 82 ms 5464 KB Output is correct
11 Correct 76 ms 5360 KB Output is correct
12 Correct 76 ms 5620 KB Output is correct
13 Correct 80 ms 5484 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 79 ms 5484 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 82 ms 5464 KB Output is correct
11 Correct 76 ms 5360 KB Output is correct
12 Correct 76 ms 5620 KB Output is correct
13 Correct 80 ms 5484 KB Output is correct
14 Correct 701 ms 6960 KB Output is correct
15 Execution timed out 4054 ms 23496 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 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 69 ms 3308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 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 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -