oj.uz

Submission #343400

# Submission time Handle Problem Language Result Execution time Memory
343400 2021-01-03T22:10:19 Z MvC Comparing Plants (IOI20_plants) C++11
27 / 100
 491 ms 15036 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 0 ms 364 KB Output is correct
4 Incorrect 0 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 0 ms 364 KB Output is correct
3 Correct 0 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 3 ms 492 KB Output is correct
7 Correct 68 ms 3436 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 68 ms 3436 KB Output is correct
11 Correct 64 ms 3308 KB Output is correct
12 Correct 65 ms 3564 KB Output is correct
13 Correct 70 ms 3436 KB Output is correct

Subtask #3
13.0 / 13.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 0 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 3 ms 492 KB Output is correct
7 Correct 68 ms 3436 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 68 ms 3436 KB Output is correct
11 Correct 64 ms 3308 KB Output is correct
12 Correct 65 ms 3564 KB Output is correct
13 Correct 70 ms 3436 KB Output is correct
14 Correct 92 ms 4184 KB Output is correct
15 Correct 489 ms 11372 KB Output is correct
16 Correct 94 ms 6528 KB Output is correct
17 Correct 491 ms 14956 KB Output is correct
18 Correct 275 ms 14444 KB Output is correct
19 Correct 279 ms 15036 KB Output is correct
20 Correct 472 ms 14956 KB Output is correct

Subtask #4
0 / 17.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 62 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 0 ms 364 KB Output is correct
4 Incorrect 0 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -