oj.uz

Submission #304266

# Submission time Handle Problem Language Result Execution time Memory
304266 2020-09-21T05:23:54 Z daniel920712 Comparing Plants (IOI20_plants) C++14
49 / 100
 4000 ms 106872 KB 
#include "plants.h"
#include <stdio.h>
#include <vector>
#include <utility>
#include <set>
using namespace std;
vector < int > all;
vector < int > ttt;
vector < int > Next[200005];
vector < pair < int , int > > con[200005];
int N,tt=0;
bool use[2000005]={0};
int Con[200005];
int what[200005];
int now=1;
struct A
{
    int l,r;
    int nxl,nxr;
    int small1,small2,small3;
    int big2;
    int add1,add2;
    int ok=0;
}Node[2000005];
void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].add1=0;
    Node[here].add2=0;
    Node[here].small1=0;
    Node[here].small3=1e9;
    Node[here].ok=0;
    if(l==r)
    {
        Node[here].small2=all[l];
        Node[here].big2=all[l];
        return ;
    }
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
    Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
    Node[here].small3=min(Node[Node[here].nxl].small3,Node[Node[here].nxr].small3);
    Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
    Node[here].big2=max(Node[Node[here].nxl].big2,Node[Node[here].nxr].big2);

}
void UPD(int here)
{
    Node[Node[here].nxl].add1+=Node[here].add1;
    Node[Node[here].nxl].small1+=Node[here].add1;
    Node[Node[here].nxr].add1+=Node[here].add1;
    Node[Node[here].nxr].small1+=Node[here].add1;
    Node[Node[here].nxr].small3+=Node[here].add1;
    Node[Node[here].nxl].small3+=Node[here].add1;
    Node[here].add1=0;
    Node[Node[here].nxl].add2+=Node[here].add2;
    Node[Node[here].nxl].small2+=Node[here].add2;
    Node[Node[here].nxr].add2+=Node[here].add2;
    Node[Node[here].nxr].small2+=Node[here].add2;
    Node[Node[here].nxl].big2+=Node[here].add2;
    Node[Node[here].nxr].big2+=Node[here].add2;
    Node[here].add2=0;
}
void cha1(int l,int r,int con,int here)
{
    if(l>r) return ;
    if(l==Node[here].l&&r==Node[here].r)
    {
        Node[here].add1+=con;
        Node[here].small1+=con;
        Node[here].small3+=con;
        return;
    }
    UPD(here);
    if(r<=(Node[here].l+Node[here].r)/2) cha1(l,r,con,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) cha1(l,r,con,Node[here].nxr);
    else
    {
        cha1(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
        cha1((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
    }
    Node[here].big2=max(Node[Node[here].nxl].big2,Node[Node[here].nxr].big2);
    Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
    Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
    Node[here].small3=min(Node[Node[here].nxl].small3,Node[Node[here].nxr].small3);
    Node[here].ok=Node[Node[here].nxl].ok||Node[Node[here].nxr].ok;
}

void cha2(int l,int r,int con,int here)
{
    if(l>r) return ;
    if(l==Node[here].l&&r==Node[here].r)
    {
        Node[here].add2+=con;
        Node[here].small2+=con;
        Node[here].big2+=con;
        if(l==r&&con==1000000000) Node[here].small3=Node[here].small1;
        return;
    }
    UPD(here);
    if(r<=(Node[here].l+Node[here].r)/2) cha2(l,r,con,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) cha2(l,r,con,Node[here].nxr);
    else
    {
        cha2(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
        cha2((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
    }
    Node[here].big2=max(Node[Node[here].nxl].big2,Node[Node[here].nxr].big2);
    Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
    Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
    Node[here].small3=min(Node[Node[here].nxl].small3,Node[Node[here].nxr].small3);
    Node[here].ok=Node[Node[here].nxl].ok||Node[Node[here].nxr].ok;
}
int Find1(int where,int here)
{
    if(Node[here].l==where&&Node[here].r==where) return Node[here].small1;
    UPD(here);
    if(where<=(Node[here].l+Node[here].r)/2) return Find1(where,Node[here].nxl);
    else return Find1(where,Node[here].nxr);
}
int Find2(int where,int here)
{
    if(Node[here].l==where&&Node[here].r==where) return Node[here].small2;
    UPD(here);
    if(where<=(Node[here].l+Node[here].r)/2) return Find2(where,Node[here].nxl);
    else return Find2(where,Node[here].nxr);
}

void New(int here)
{
    if(Node[here].l==Node[here].r)
    {
        ttt.push_back(Node[here].l);
        return;
    }
    UPD(here);
    if(Node[Node[here].nxl].small2==0) New(Node[here].nxl);
    if(Node[Node[here].nxr].small2==0) New(Node[here].nxr);

}
int New2(int here)
{
    //printf("%d %d %d %d %d %d\n",Node[here].l,Node[here].r,Node[Node[here].nxl].big2,Node[Node[here].nxl].small1,Node[Node[here].nxr].big2,Node[Node[here].nxr].small1);
    if(Node[here].l==Node[here].r) return Node[here].l;
    UPD(here);
    if(Node[Node[here].nxl].small3==0&&Node[Node[here].nxl].big2>N) return New2(Node[here].nxl);
    else return New2(Node[here].nxr);

}
bool F(int a,int b)
{
    if(a==b) return 1;
    if(use[a]) return 0;
    use[a]=1;
    for(auto i:Next[a]) if(F(i,b)) return 1;
    return 0;
}
void init(int k,vector<int> r)
{
    int a=0,b=0,i,j,ok=0,l,t,t2,x,ll,rr;
    all=r;
    N=r.size();
    if(k==2)
    {
        tt=1;
        for(i=0;i<N;i++)
        {
            if(r[(i+N-1)%N]!=r[i])
            {
                b=0;
                a++;
                con[i].push_back(make_pair(a,0));
                for(j=(i+1)%N;r[(j+N-1)%N]==r[i];j=(j+1)%N)
                {
                    if(j==N-1) ok=1;
                    if(r[i]==0) b--;
                    else b++;
                    con[j].push_back(make_pair(a,b));
                }
            }
        }
    }
    else if(N<=300)
    {
        tt=2;
        for(i=0;i<N;i++)
        {
            if(r[i]==0)
            {
                for(j=1;j<k;j++)
                {
                    t=(i+j)%N;
                    Con[t]++;
                }
            }
        }
        for(i=0;i<N;i++)
        {
            for(j=0;j<N;j++)
            {
                if(use[j]==0&&Con[j]==0&&r[j]==0)
                {
                    x=j;
                    break;
                }
            }

            use[x]=1;
            for(j=1;j<k;j++)
            {
                t=(x+j)%N;
                Con[t]--;
                if(!use[t]) Next[t].push_back(x);
                else Next[x].push_back(t);
            }
            for(j=1;j<k;j++)
            {
                t=(x-j+2*N)%N;
                r[t]--;
                if(use[t]) Next[x].push_back(t);
                else Next[t].push_back(x);
                if(r[t]==0)
                {
                    for(l=1;l<k;l++)
                    {
                        t2=(t+l)%N;
                        Con[t2]++;
                    }
                }
            }
        }
    }
    else
    {
        build(0,N-1,0);
        ttt.clear();
        New(0);
        for(auto t:ttt)
        {
            cha2(t,t,1e9,0);
            t2=(t+k-1)%N;
            if(t2>=t) cha1(t+1,t2,1,0);
            else
            {
                cha1(t+1,N-1,1,0);
                cha1(0,t2,1,0);
            }
        }
        for(i=0;i<N;i++)
        {
            x=New2(0);
            cha1(x,x,1e9,0);
            what[x]=i;
            t=(x+k-1)%N;
            if(t>=x) cha1(x+1,t,-1,0);
            else
            {
                cha1(x+1,N-1,-1,0);
                cha1(0,t,-1,0);
            }
            ll=(x-(k-1)+N)%N;
            rr=(x-1+N)%N;
            if(rr>=ll) cha2(ll,rr,-1,0);
            else
            {
                cha2(ll,N-1,-1,0);
                cha2(0,rr,-1,0);
            }
            ttt.clear();
            New(0);
            for(auto t:ttt)
            {
                cha2(t,t,1e9,0);
                t2=(t+k-1)%N;
                if(t2>=t) cha1(t+1,t2,1,0);
                else
                {
                    cha1(t+1,N-1,1,0);
                    cha1(0,t2,1,0);
                }
            }

        }
    }
	return;
}

int compare_plants(int x, int y)
{
    int i;
    if(tt==1)
    {
        for(auto i:con[x])
        {
            for(auto j:con[y])
            {
                if(i.first==j.first)
                {
                    if(i.second<j.second) return -1;
                    return 1;
                }
            }
        }
        return 0;

    }
    else if(tt==2)
    {
        for(i=0;i<N;i++) use[i]=0;
        if(F(x,y)) return -1;
        for(i=0;i<N;i++) use[i]=0;
        if(F(y,x)) return 1;
        return 0;
    }
    else
    {
        if(what[x]<what[y]) return 1;
        else return -1;
    }
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:163:21: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  163 |     int a=0,b=0,i,j,ok=0,l,t,t2,x,ll,rr;
      |                     ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 95736 KB Output is correct
2 Correct 47 ms 95864 KB Output is correct
3 Correct 47 ms 95736 KB Output is correct
4 Correct 46 ms 95820 KB Output is correct
5 Correct 47 ms 95736 KB Output is correct
6 Correct 123 ms 98680 KB Output is correct
7 Correct 160 ms 99448 KB Output is correct
8 Correct 182 ms 106744 KB Output is correct
9 Correct 179 ms 106872 KB Output is correct
10 Correct 180 ms 106744 KB Output is correct
11 Correct 185 ms 106744 KB Output is correct
12 Correct 177 ms 106744 KB Output is correct
13 Correct 176 ms 106744 KB Output is correct
14 Correct 177 ms 106744 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 95740 KB Output is correct
2 Correct 48 ms 95788 KB Output is correct
3 Correct 47 ms 95864 KB Output is correct
4 Correct 46 ms 95864 KB Output is correct
5 Correct 53 ms 95864 KB Output is correct
6 Correct 52 ms 95864 KB Output is correct
7 Correct 145 ms 98808 KB Output is correct
8 Correct 98 ms 95992 KB Output is correct
9 Correct 53 ms 95864 KB Output is correct
10 Correct 142 ms 98824 KB Output is correct
11 Correct 140 ms 98680 KB Output is correct
12 Correct 145 ms 98808 KB Output is correct
13 Correct 144 ms 98808 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 95740 KB Output is correct
2 Correct 48 ms 95788 KB Output is correct
3 Correct 47 ms 95864 KB Output is correct
4 Correct 46 ms 95864 KB Output is correct
5 Correct 53 ms 95864 KB Output is correct
6 Correct 52 ms 95864 KB Output is correct
7 Correct 145 ms 98808 KB Output is correct
8 Correct 98 ms 95992 KB Output is correct
9 Correct 53 ms 95864 KB Output is correct
10 Correct 142 ms 98824 KB Output is correct
11 Correct 140 ms 98680 KB Output is correct
12 Correct 145 ms 98808 KB Output is correct
13 Correct 144 ms 98808 KB Output is correct
14 Correct 237 ms 99044 KB Output is correct
15 Correct 1595 ms 101368 KB Output is correct
16 Correct 230 ms 98936 KB Output is correct
17 Correct 1621 ms 101368 KB Output is correct
18 Correct 1203 ms 102000 KB Output is correct
19 Correct 1245 ms 101624 KB Output is correct
20 Correct 1495 ms 101368 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 95864 KB Output is correct
2 Correct 47 ms 95864 KB Output is correct
3 Correct 125 ms 98680 KB Output is correct
4 Correct 934 ms 101744 KB Output is correct
5 Correct 1072 ms 101496 KB Output is correct
6 Correct 1332 ms 101368 KB Output is correct
7 Correct 1513 ms 101368 KB Output is correct
8 Correct 1616 ms 101532 KB Output is correct
9 Correct 978 ms 101748 KB Output is correct
10 Correct 976 ms 101448 KB Output is correct
11 Correct 173 ms 106744 KB Output is correct
12 Correct 1018 ms 101368 KB Output is correct
13 Correct 1196 ms 102124 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 95736 KB Output is correct
2 Correct 48 ms 95736 KB Output is correct
3 Correct 47 ms 95736 KB Output is correct
4 Correct 47 ms 95864 KB Output is correct
5 Correct 48 ms 95864 KB Output is correct
6 Correct 52 ms 95872 KB Output is correct
7 Correct 178 ms 96460 KB Output is correct
8 Correct 1761 ms 96888 KB Output is correct
9 Correct 273 ms 96504 KB Output is correct
10 Correct 1730 ms 96828 KB Output is correct
11 Correct 206 ms 96504 KB Output is correct
12 Correct 432 ms 96504 KB Output is correct
13 Execution timed out 4081 ms 97528 KB Time limit exceeded

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 95864 KB Output is correct
2 Correct 48 ms 95756 KB Output is correct
3 Correct 47 ms 95736 KB Output is correct
4 Correct 47 ms 95864 KB Output is correct
5 Incorrect 50 ms 95864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 95736 KB Output is correct
2 Correct 47 ms 95864 KB Output is correct
3 Correct 47 ms 95736 KB Output is correct
4 Correct 46 ms 95820 KB Output is correct
5 Correct 47 ms 95736 KB Output is correct
6 Correct 123 ms 98680 KB Output is correct
7 Correct 160 ms 99448 KB Output is correct
8 Correct 182 ms 106744 KB Output is correct
9 Correct 179 ms 106872 KB Output is correct
10 Correct 180 ms 106744 KB Output is correct
11 Correct 185 ms 106744 KB Output is correct
12 Correct 177 ms 106744 KB Output is correct
13 Correct 176 ms 106744 KB Output is correct
14 Correct 177 ms 106744 KB Output is correct
15 Correct 46 ms 95740 KB Output is correct
16 Correct 48 ms 95788 KB Output is correct
17 Correct 47 ms 95864 KB Output is correct
18 Correct 46 ms 95864 KB Output is correct
19 Correct 53 ms 95864 KB Output is correct
20 Correct 52 ms 95864 KB Output is correct
21 Correct 145 ms 98808 KB Output is correct
22 Correct 98 ms 95992 KB Output is correct
23 Correct 53 ms 95864 KB Output is correct
24 Correct 142 ms 98824 KB Output is correct
25 Correct 140 ms 98680 KB Output is correct
26 Correct 145 ms 98808 KB Output is correct
27 Correct 144 ms 98808 KB Output is correct
28 Correct 237 ms 99044 KB Output is correct
29 Correct 1595 ms 101368 KB Output is correct
30 Correct 230 ms 98936 KB Output is correct
31 Correct 1621 ms 101368 KB Output is correct
32 Correct 1203 ms 102000 KB Output is correct
33 Correct 1245 ms 101624 KB Output is correct
34 Correct 1495 ms 101368 KB Output is correct
35 Correct 46 ms 95864 KB Output is correct
36 Correct 47 ms 95864 KB Output is correct
37 Correct 125 ms 98680 KB Output is correct
38 Correct 934 ms 101744 KB Output is correct
39 Correct 1072 ms 101496 KB Output is correct
40 Correct 1332 ms 101368 KB Output is correct
41 Correct 1513 ms 101368 KB Output is correct
42 Correct 1616 ms 101532 KB Output is correct
43 Correct 978 ms 101748 KB Output is correct
44 Correct 976 ms 101448 KB Output is correct
45 Correct 173 ms 106744 KB Output is correct
46 Correct 1018 ms 101368 KB Output is correct
47 Correct 1196 ms 102124 KB Output is correct
48 Correct 47 ms 95736 KB Output is correct
49 Correct 48 ms 95736 KB Output is correct
50 Correct 47 ms 95736 KB Output is correct
51 Correct 47 ms 95864 KB Output is correct
52 Correct 48 ms 95864 KB Output is correct
53 Correct 52 ms 95872 KB Output is correct
54 Correct 178 ms 96460 KB Output is correct
55 Correct 1761 ms 96888 KB Output is correct
56 Correct 273 ms 96504 KB Output is correct
57 Correct 1730 ms 96828 KB Output is correct
58 Correct 206 ms 96504 KB Output is correct
59 Correct 432 ms 96504 KB Output is correct
60 Execution timed out 4081 ms 97528 KB Time limit exceeded