oj.uz

Submission #304071

# Submission time Handle Problem Language Result Execution time Memory
304071 2020-09-21T02:21:36 Z daniel920712 Comparing Plants (IOI20_plants) C++14
49 / 100
 1636 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);

}
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(k==2)
        {
            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
        {
            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);
                /*printf("%d\n",x);
                for(j=0;j<N;j++)
                {
                    if(Find1(j,0)==0&&Find2(j,0)>N)
                    {
                        x=j;
                        break;
                    }
                }*/
                //printf("%d\n",x);
                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;
}
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;
}
int compare_plants(int x, int y)
{
    int i;
    if(tt)
    {
        for(auto i:con[x])
        {
            for(auto j:con[y])
            {
                if(i.first==j.first)
                {
                    if(i.second<j.second) return -1;
                    return 1;
                }
            }
        }

    }
    else
    {
        if(what[x]<what[y]) return 1;
        else return -1;
    }

	return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 95736 KB Output is correct
2 Correct 52 ms 95768 KB Output is correct
3 Correct 51 ms 95736 KB Output is correct
4 Correct 52 ms 95740 KB Output is correct
5 Correct 52 ms 95744 KB Output is correct
6 Correct 123 ms 98680 KB Output is correct
7 Correct 138 ms 99576 KB Output is correct
8 Correct 189 ms 106744 KB Output is correct
9 Correct 190 ms 106744 KB Output is correct
10 Correct 186 ms 106744 KB Output is correct
11 Correct 186 ms 106744 KB Output is correct
12 Correct 194 ms 106872 KB Output is correct
13 Correct 186 ms 106744 KB Output is correct
14 Correct 189 ms 106744 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 95816 KB Output is correct
2 Correct 52 ms 95736 KB Output is correct
3 Correct 53 ms 95736 KB Output is correct
4 Correct 51 ms 95736 KB Output is correct
5 Correct 53 ms 95736 KB Output is correct
6 Correct 57 ms 95992 KB Output is correct
7 Correct 146 ms 98808 KB Output is correct
8 Correct 53 ms 95872 KB Output is correct
9 Correct 56 ms 95880 KB Output is correct
10 Correct 149 ms 98812 KB Output is correct
11 Correct 140 ms 98680 KB Output is correct
12 Correct 143 ms 98808 KB Output is correct
13 Correct 144 ms 98812 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 95816 KB Output is correct
2 Correct 52 ms 95736 KB Output is correct
3 Correct 53 ms 95736 KB Output is correct
4 Correct 51 ms 95736 KB Output is correct
5 Correct 53 ms 95736 KB Output is correct
6 Correct 57 ms 95992 KB Output is correct
7 Correct 146 ms 98808 KB Output is correct
8 Correct 53 ms 95872 KB Output is correct
9 Correct 56 ms 95880 KB Output is correct
10 Correct 149 ms 98812 KB Output is correct
11 Correct 140 ms 98680 KB Output is correct
12 Correct 143 ms 98808 KB Output is correct
13 Correct 144 ms 98812 KB Output is correct
14 Correct 231 ms 98936 KB Output is correct
15 Correct 1606 ms 101368 KB Output is correct
16 Correct 230 ms 98936 KB Output is correct
17 Correct 1636 ms 101496 KB Output is correct
18 Correct 1216 ms 102000 KB Output is correct
19 Correct 1258 ms 101396 KB Output is correct
20 Correct 1507 ms 101240 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 95740 KB Output is correct
2 Correct 51 ms 95736 KB Output is correct
3 Correct 129 ms 98736 KB Output is correct
4 Correct 939 ms 101728 KB Output is correct
5 Correct 1069 ms 101436 KB Output is correct
6 Correct 1337 ms 101440 KB Output is correct
7 Correct 1526 ms 101496 KB Output is correct
8 Correct 1614 ms 101352 KB Output is correct
9 Correct 982 ms 101748 KB Output is correct
10 Correct 978 ms 101496 KB Output is correct
11 Correct 184 ms 106744 KB Output is correct
12 Correct 1033 ms 101404 KB Output is correct
13 Correct 1193 ms 101996 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 95736 KB Output is correct
2 Correct 52 ms 95932 KB Output is correct
3 Correct 54 ms 95736 KB Output is correct
4 Correct 51 ms 95740 KB Output is correct
5 Incorrect 52 ms 95736 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 95736 KB Output is correct
2 Correct 51 ms 95736 KB Output is correct
3 Correct 53 ms 95736 KB Output is correct
4 Incorrect 52 ms 95740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 95736 KB Output is correct
2 Correct 52 ms 95768 KB Output is correct
3 Correct 51 ms 95736 KB Output is correct
4 Correct 52 ms 95740 KB Output is correct
5 Correct 52 ms 95744 KB Output is correct
6 Correct 123 ms 98680 KB Output is correct
7 Correct 138 ms 99576 KB Output is correct
8 Correct 189 ms 106744 KB Output is correct
9 Correct 190 ms 106744 KB Output is correct
10 Correct 186 ms 106744 KB Output is correct
11 Correct 186 ms 106744 KB Output is correct
12 Correct 194 ms 106872 KB Output is correct
13 Correct 186 ms 106744 KB Output is correct
14 Correct 189 ms 106744 KB Output is correct
15 Correct 53 ms 95816 KB Output is correct
16 Correct 52 ms 95736 KB Output is correct
17 Correct 53 ms 95736 KB Output is correct
18 Correct 51 ms 95736 KB Output is correct
19 Correct 53 ms 95736 KB Output is correct
20 Correct 57 ms 95992 KB Output is correct
21 Correct 146 ms 98808 KB Output is correct
22 Correct 53 ms 95872 KB Output is correct
23 Correct 56 ms 95880 KB Output is correct
24 Correct 149 ms 98812 KB Output is correct
25 Correct 140 ms 98680 KB Output is correct
26 Correct 143 ms 98808 KB Output is correct
27 Correct 144 ms 98812 KB Output is correct
28 Correct 231 ms 98936 KB Output is correct
29 Correct 1606 ms 101368 KB Output is correct
30 Correct 230 ms 98936 KB Output is correct
31 Correct 1636 ms 101496 KB Output is correct
32 Correct 1216 ms 102000 KB Output is correct
33 Correct 1258 ms 101396 KB Output is correct
34 Correct 1507 ms 101240 KB Output is correct
35 Correct 51 ms 95740 KB Output is correct
36 Correct 51 ms 95736 KB Output is correct
37 Correct 129 ms 98736 KB Output is correct
38 Correct 939 ms 101728 KB Output is correct
39 Correct 1069 ms 101436 KB Output is correct
40 Correct 1337 ms 101440 KB Output is correct
41 Correct 1526 ms 101496 KB Output is correct
42 Correct 1614 ms 101352 KB Output is correct
43 Correct 982 ms 101748 KB Output is correct
44 Correct 978 ms 101496 KB Output is correct
45 Correct 184 ms 106744 KB Output is correct
46 Correct 1033 ms 101404 KB Output is correct
47 Correct 1193 ms 101996 KB Output is correct
48 Correct 51 ms 95736 KB Output is correct
49 Correct 52 ms 95932 KB Output is correct
50 Correct 54 ms 95736 KB Output is correct
51 Correct 51 ms 95740 KB Output is correct
52 Incorrect 52 ms 95736 KB Output isn't correct
53 Halted 0 ms 0 KB -