oj.uz

Submission #305666

# Submission time Handle Problem Language Result Execution time Memory
305666 2020-09-23T18:53:30 Z baluteshih Comparing Plants (IOI20_plants) C++14
100 / 100
 1872 ms 158696 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(),v.end()
#define SZ(a) ((int)a.size())
#define pb push_back

const int INF=1e9;
struct node
{
    int pa;
    ll dis;
    node operator+(const node &a)const{
        return node{a.pa,dis+a.dis};
    }
}Rtr[200005][20],Ltr[200005][20];
pii seg3[1600005],seg4[1600005];
int seg1[800005],seg2[800005],lazy1[800005],lazy2[800005];
int layer[400005];
vector<int> store[200005];

void build(int l,int r,int rt,const vector<int> &v,int *seg)
{
    if(l==r)
        return seg[rt]=v[l],void();
    int mid=(l+r)>>1;
    build(l,mid,rt<<1,v,seg),build(mid+1,r,rt<<1|1,v,seg);
    seg[rt]=min(seg[rt<<1],seg[rt<<1|1]);
}

void down(int rt,int *seg,int *lazy)
{
    if(lazy[rt])
    {
        seg[rt<<1]+=lazy[rt],lazy[rt<<1]+=lazy[rt];
        seg[rt<<1|1]+=lazy[rt],lazy[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }
}

void modify(int L,int R,int l,int r,int rt,int val,int *seg,int *lazy)
{
    if(l!=r) down(rt,seg,lazy);
    if(L<=l&&R>=r)
        return lazy[rt]+=val,seg[rt]+=val,void();
    int mid=(l+r)>>1;
    if(L<=mid)
        modify(L,R,l,mid,rt<<1,val,seg,lazy);
    if(R>mid)
        modify(L,R,mid+1,r,rt<<1|1,val,seg,lazy);
    seg[rt]=min(seg[rt<<1],seg[rt<<1|1]);
}

int query(int l,int r,int rt,int *seg,int *lazy)
{
    if(l!=r) down(rt,seg,lazy);
    if(l==r)
        return l;
    int mid=(l+r)>>1;
    if(seg[rt<<1]<=seg[rt<<1|1])
        return query(l,mid,rt<<1,seg,lazy);
    return query(mid+1,r,rt<<1|1,seg,lazy);
}

void dfs(int l,int r,int rt,int *seg,int *lazy,vector<int> &rst)
{
    if(l!=r) down(rt,seg,lazy);
    if(l==r)
        return rst.pb(l);
    int mid=(l+r)>>1;
    if(seg[rt<<1]==0)
        dfs(l,mid,rt<<1,seg,lazy,rst);
    if(seg[rt<<1|1]==0)
        dfs(mid+1,r,rt<<1|1,seg,lazy,rst);
}

void build2(int l,int r,int rt)
{
    seg3[rt]=pii(INF,l);
    if(l==r)
        return;
    int mid=(l+r)>>1;
    build2(l,mid,rt<<1),build2(mid+1,r,rt<<1|1);
}

void modify2(int x,int l,int r,int rt,int val)
{
    if(l==r)
        return seg3[rt]=pii(val,l),void();
    int mid=(l+r)>>1;
    if(x<=mid)
        modify2(x,l,mid,rt<<1,val);
    else
        modify2(x,mid+1,r,rt<<1|1,val);
    seg3[rt]=min(seg3[rt<<1],seg3[rt<<1|1]);
}

pii query2(int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)
        return seg3[rt];
    int mid=(l+r)>>1;
    if(R<=mid)
        return query2(L,R,l,mid,rt<<1);
    if(L>mid)
        return query2(L,R,mid+1,r,rt<<1|1);
    return min(query2(L,R,l,mid,rt<<1),query2(L,R,mid+1,r,rt<<1|1));
}

int arr[200005],K,n,L;

void init(int k, vector<int> r)
{
    n=SZ(r),K=k,L=__lg(n);
    int ly=0;
	build(0,n-1,1,r,seg1),build(0,n-1,1,vector<int>(n,INF),seg2);
    for(int i=0;i<n;++ly)
    {
        while(seg1[1]==0)
        {
            int u=query(0,n-1,1,seg1,lazy1);
            modify(u,u,0,n-1,1,INF,seg1,lazy1),modify(u,u,0,n-1,1,-INF,seg2,lazy2);
            if(u+k<=n)
                modify(u+1,u+k-1,0,n-1,1,1,seg2,lazy2);
            else
            {
                if(u<n-1)
                    modify(u+1,n-1,0,n-1,1,1,seg2,lazy2);
                modify(0,k-n+u-1,0,n-1,1,1,seg2,lazy2);
            }
        }
        vector<int> rst;
        dfs(0,n-1,1,seg2,lazy2,rst);
        for(int u:rst)
        {
            if(u>=k-1)
                modify(u-k+1,u,0,n-1,1,-1,seg1,lazy1);
            else
                modify(0,u,0,n-1,1,-1,seg1,lazy1),modify(n-(k-u-1),n-1,0,n-1,1,-1,seg1,lazy1);
            if(u+k<=n)
                modify(u+1,u+k-1,0,n-1,1,-1,seg2,lazy2);
            else
            {
                if(u<n-1)
                    modify(u+1,n-1,0,n-1,1,-1,seg2,lazy2);
                modify(0,k-n+u-1,0,n-1,1,-1,seg2,lazy2);
            }
            modify(u,u,0,n-1,1,INF,seg2,lazy2);
            layer[u]=ly;
        }
        i+=SZ(rst),store[ly].swap(rst);
    }
    for(int i=0;i<n;++i)
        layer[i+n]=layer[i];
    build2(0,2*n-1,1);
    for(int i=ly-1;i>=0;--i)
    {
        for(int u:store[i])
        {
            pii tmp=query2(u+n-k+1,u+n,0,2*n-1,1);
            if(tmp.X==INF)
                Ltr[u][0]=node{u,0};
            else 
                Ltr[u][0]=node{tmp.Y%n,u+n-tmp.Y};
            tmp=query2(u,u+k-1,0,2*n-1,1);
            if(tmp.X==INF)
                Rtr[u][0]=node{u,0};
            else
                Rtr[u][0]=node{tmp.Y%n,tmp.Y-u};
        }
        for(int u:store[i])
            modify2(u,0,2*n-1,1,layer[u]),modify2(u+n,0,2*n-1,1,layer[u]);
    }
    for(int t=1;t<=L;++t)
        for(int i=0;i<n;++i)
            Ltr[i][t]=Ltr[i][t-1]+Ltr[Ltr[i][t-1].pa][t-1],Rtr[i][t]=Rtr[i][t-1]+Rtr[Rtr[i][t-1].pa][t-1];
}

int compare_plants(int x, int y)
{
    if(layer[x]==layer[y]) return 0;
    int rt=1,tar,nw;
    ll dis;
    if(layer[x]>layer[y])
        swap(x,y),rt=-1;
    if(x>y)
        tar=y+n;
    else
        tar=y;
    nw=x;
    if(nw+K>tar)
        return rt;
    dis=0;
    for(int i=L;i>=0;--i)
        if(x+dis+Rtr[nw][i].dis+K<=tar)
            dis+=Rtr[nw][i].dis,nw=Rtr[nw][i].pa;
    dis+=Rtr[nw][0].dis,nw=Rtr[nw][0].pa;
    if(layer[y]>layer[nw]&&x+dis+K>tar)
        return rt;
    nw=x;
    if(x<y)
        tar=y-n;
    else
        tar=y;
    if(nw-K<tar)
        return rt;
    dis=0;
    for(int i=L;i>=0;--i)
        if(x+dis-Ltr[nw][i].dis-K>=tar)
            dis-=Ltr[nw][i].dis,nw=Ltr[nw][i].pa;
    dis-=Ltr[nw][0].dis,nw=Ltr[nw][0].pa;
    if(layer[y]>layer[nw]&&x+dis-K<tar)
        return rt;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 74 ms 7928 KB Output is correct
7 Correct 209 ms 22776 KB Output is correct
8 Correct 961 ms 152168 KB Output is correct
9 Correct 1033 ms 152292 KB Output is correct
10 Correct 1041 ms 152552 KB Output is correct
11 Correct 1002 ms 152932 KB Output is correct
12 Correct 1006 ms 154568 KB Output is correct
13 Correct 1032 ms 157544 KB Output is correct
14 Correct 1096 ms 157544 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 9 ms 5888 KB Output is correct
7 Correct 100 ms 11768 KB Output is correct
8 Correct 6 ms 5248 KB Output is correct
9 Correct 9 ms 5844 KB Output is correct
10 Correct 98 ms 11768 KB Output is correct
11 Correct 100 ms 11772 KB Output is correct
12 Correct 97 ms 11896 KB Output is correct
13 Correct 95 ms 11768 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 9 ms 5888 KB Output is correct
7 Correct 100 ms 11768 KB Output is correct
8 Correct 6 ms 5248 KB Output is correct
9 Correct 9 ms 5844 KB Output is correct
10 Correct 98 ms 11768 KB Output is correct
11 Correct 100 ms 11772 KB Output is correct
12 Correct 97 ms 11896 KB Output is correct
13 Correct 95 ms 11768 KB Output is correct
14 Correct 204 ms 23544 KB Output is correct
15 Correct 1816 ms 158496 KB Output is correct
16 Correct 209 ms 23520 KB Output is correct
17 Correct 1807 ms 158520 KB Output is correct
18 Correct 1193 ms 158496 KB Output is correct
19 Correct 1173 ms 158696 KB Output is correct
20 Correct 1683 ms 158596 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 150 ms 9364 KB Output is correct
4 Correct 1164 ms 156236 KB Output is correct
5 Correct 1321 ms 153940 KB Output is correct
6 Correct 1735 ms 154588 KB Output is correct
7 Correct 1803 ms 155412 KB Output is correct
8 Correct 1872 ms 158180 KB Output is correct
9 Correct 1142 ms 153804 KB Output is correct
10 Correct 1168 ms 157412 KB Output is correct
11 Correct 1033 ms 157540 KB Output is correct
12 Correct 1249 ms 158444 KB Output is correct
13 Correct 1256 ms 158440 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5152 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 6 ms 5248 KB Output is correct
7 Correct 22 ms 5888 KB Output is correct
8 Correct 21 ms 6016 KB Output is correct
9 Correct 24 ms 5888 KB Output is correct
10 Correct 21 ms 6016 KB Output is correct
11 Correct 25 ms 5888 KB Output is correct
12 Correct 23 ms 5888 KB Output is correct
13 Correct 20 ms 6016 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 7 ms 5888 KB Output is correct
6 Correct 1376 ms 153192 KB Output is correct
7 Correct 1583 ms 153576 KB Output is correct
8 Correct 1656 ms 153728 KB Output is correct
9 Correct 1800 ms 158060 KB Output is correct
10 Correct 977 ms 153616 KB Output is correct
11 Correct 1439 ms 155492 KB Output is correct
12 Correct 1006 ms 156264 KB Output is correct
13 Correct 1175 ms 154212 KB Output is correct
14 Correct 1504 ms 154728 KB Output is correct
15 Correct 1700 ms 155496 KB Output is correct
16 Correct 1050 ms 156936 KB Output is correct
17 Correct 1120 ms 154988 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 74 ms 7928 KB Output is correct
7 Correct 209 ms 22776 KB Output is correct
8 Correct 961 ms 152168 KB Output is correct
9 Correct 1033 ms 152292 KB Output is correct
10 Correct 1041 ms 152552 KB Output is correct
11 Correct 1002 ms 152932 KB Output is correct
12 Correct 1006 ms 154568 KB Output is correct
13 Correct 1032 ms 157544 KB Output is correct
14 Correct 1096 ms 157544 KB Output is correct
15 Correct 4 ms 5120 KB Output is correct
16 Correct 3 ms 5120 KB Output is correct
17 Correct 4 ms 5120 KB Output is correct
18 Correct 4 ms 5120 KB Output is correct
19 Correct 4 ms 5120 KB Output is correct
20 Correct 9 ms 5888 KB Output is correct
21 Correct 100 ms 11768 KB Output is correct
22 Correct 6 ms 5248 KB Output is correct
23 Correct 9 ms 5844 KB Output is correct
24 Correct 98 ms 11768 KB Output is correct
25 Correct 100 ms 11772 KB Output is correct
26 Correct 97 ms 11896 KB Output is correct
27 Correct 95 ms 11768 KB Output is correct
28 Correct 204 ms 23544 KB Output is correct
29 Correct 1816 ms 158496 KB Output is correct
30 Correct 209 ms 23520 KB Output is correct
31 Correct 1807 ms 158520 KB Output is correct
32 Correct 1193 ms 158496 KB Output is correct
33 Correct 1173 ms 158696 KB Output is correct
34 Correct 1683 ms 158596 KB Output is correct
35 Correct 4 ms 5120 KB Output is correct
36 Correct 4 ms 5120 KB Output is correct
37 Correct 150 ms 9364 KB Output is correct
38 Correct 1164 ms 156236 KB Output is correct
39 Correct 1321 ms 153940 KB Output is correct
40 Correct 1735 ms 154588 KB Output is correct
41 Correct 1803 ms 155412 KB Output is correct
42 Correct 1872 ms 158180 KB Output is correct
43 Correct 1142 ms 153804 KB Output is correct
44 Correct 1168 ms 157412 KB Output is correct
45 Correct 1033 ms 157540 KB Output is correct
46 Correct 1249 ms 158444 KB Output is correct
47 Correct 1256 ms 158440 KB Output is correct
48 Correct 4 ms 5120 KB Output is correct
49 Correct 4 ms 5152 KB Output is correct
50 Correct 4 ms 5120 KB Output is correct
51 Correct 4 ms 5120 KB Output is correct
52 Correct 4 ms 5120 KB Output is correct
53 Correct 6 ms 5248 KB Output is correct
54 Correct 22 ms 5888 KB Output is correct
55 Correct 21 ms 6016 KB Output is correct
56 Correct 24 ms 5888 KB Output is correct
57 Correct 21 ms 6016 KB Output is correct
58 Correct 25 ms 5888 KB Output is correct
59 Correct 23 ms 5888 KB Output is correct
60 Correct 20 ms 6016 KB Output is correct
61 Correct 97 ms 9208 KB Output is correct
62 Correct 208 ms 22776 KB Output is correct
63 Correct 1107 ms 152940 KB Output is correct
64 Correct 1389 ms 153448 KB Output is correct
65 Correct 1715 ms 153572 KB Output is correct
66 Correct 1757 ms 153576 KB Output is correct
67 Correct 1811 ms 157984 KB Output is correct
68 Correct 1073 ms 154088 KB Output is correct
69 Correct 1540 ms 155368 KB Output is correct
70 Correct 1141 ms 155496 KB Output is correct
71 Correct 1284 ms 154212 KB Output is correct
72 Correct 1629 ms 154596 KB Output is correct
73 Correct 1759 ms 155624 KB Output is correct
74 Correct 1194 ms 153192 KB Output is correct
75 Correct 1157 ms 158052 KB Output is correct