oj.uz

Submission #1107791

# Submission time Handle Problem Language Result Execution time Memory
1107791 2024-11-02T05:45:42 Z Aviansh Horses (IOI15_horses) C++17
100 / 100
 194 ms 37192 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

int n;
int *x;
int *y;
int mod = 1e9+7;

template <class T> class segTree{
    private:
        int n;
        T *st;
    public:
        void realMakeST(int *arr, int l, int r, int ind){
            if(l==r){
                st[ind]=arr[l];
            }
            else{
                int mid = (l+r)/2;
                realMakeST(arr,l,mid,ind*2+1);
                realMakeST(arr,mid+1,r,ind*2+2);
                st[ind]=st[ind*2+1]*st[ind*2+2];
                st[ind]%=mod;
            }
        }
        segTree(){
            //aise hi
        }
        segTree(int *arr, int siz){
            int x = (int)pow(2,ceil(log2(siz)));
            n=siz-1;
            x*=2;
            st=new T[x];
            realMakeST(arr,0,n,0);
        }
        void realUpdate(int l, int r, int ind, int pos, int val){
            if(pos<l||pos>r){
                return;
            }
            if(l==r){
                st[ind]=val;
                return;
            }
            int mid = (l+r)/2;
            realUpdate(l,mid,2*ind+1,pos,val);
            realUpdate(mid+1,r,2*ind+2,pos,val);
            st[ind]=st[ind*2+1]*st[ind*2+2];
            st[ind]%=mod;
        }
        void update(int ind, int val){
            realUpdate(0,n,0,ind,val);
        }

        T realQuery(int l, int r, int s, int e, int ind){
            if(e<l||s>r){
                return 1;
            }
            if(s<=l&&r<=e){
                return st[ind];
            }
            int mid = (l+r)/2;
            return (realQuery(l,mid,s,e,2*ind+1)*realQuery(mid+1,r,s,e,2*ind+2))%mod;
        }

        T query(int s,int e){
            return realQuery(0,n,s,e,0);
        }
};


template <class T> class segTreeMax{
    private:
        int n;
        T *st;
    public:
        void realMakeST(int *arr, int l, int r, int ind){
            if(l==r){
                st[ind]=arr[l];
            }
            else{
                int mid = (l+r)/2;
                realMakeST(arr,l,mid,ind*2+1);
                realMakeST(arr,mid+1,r,ind*2+2);
                st[ind]=max(st[ind*2+1],st[ind*2+2]);
                st[ind]%=mod;
            }
        }
        segTreeMax(){
            //aise hi
        }
        segTreeMax(int *arr, int siz){
            int x = (int)pow(2,ceil(log2(siz)));
            n=siz-1;
            x*=2;
            st=new T[x];
            realMakeST(arr,0,n,0);
        }
        void realUpdate(int l, int r, int ind, int pos, int val){
            if(pos<l||pos>r){
                return;
            }
            if(l==r){
                st[ind]=val;
                return;
            }
            int mid = (l+r)/2;
            realUpdate(l,mid,2*ind+1,pos,val);
            realUpdate(mid+1,r,2*ind+2,pos,val);
            st[ind]=max(st[ind*2+1],st[ind*2+2]);
            st[ind]%=mod;
        }
        void update(int ind, int val){
            realUpdate(0,n,0,ind,val);
        }

        T realQuery(int l, int r, int s, int e, int ind){
            if(e<l||s>r){
                return 1;
            }
            if(s<=l&&r<=e){
                return st[ind];
            }
            int mid = (l+r)/2;
            return max(realQuery(l,mid,s,e,2*ind+1),realQuery(mid+1,r,s,e,2*ind+2));
        }

        T query(int s,int e){
            return realQuery(0,n,s,e,0);
        }
};

int t = 1;
int *temp = &t;

segTree<long long> st(temp,1);
segTreeMax<long long> stmax(temp,1);
set<pair<int,int>>ones;

int finans(){
    int mx = n-1;
    long long curr = 1;
    int mxy = y[n-1];
    //cout << "here1" << endl;
    set<pair<int,int>>::iterator it = ones.end();
    //cout << "here2" << endl;
    //cout << "ones.size: " << ones.size() << endl;
    bool over = (ones.size()==0);
    if(!over)
        --it;
    for(int i = n-1;i>=0;i--){
        if(!over&&i==(*it).second){
            i=(*it).first;
            int cury = 0;
            if((*it).second-(*it).first<=20){
                for(int i = (*it).first;i<=(*it).second;i++){
                    cury=max(cury,y[i]);
                }
            }
            else{
                cury = stmax.query((*it).first,(*it).second);
            }
            if(cury>curr){
                mx=i;
                curr=cury;
                mxy=cury;
            }
            if(it==ones.begin()){
                over=1;
            }
            it--;
            if(curr>=1e9){
                break;
            }
            continue;
        }
        if(y[i]>curr){
            mx=i;
            curr=y[i];
            mxy=y[i];
        }
        curr*=x[i];
        //cout << i << endl;
        if(curr>=1e9){
            break;
        }
    }
    //cout << "returning: " << (1LL*st.query(0,mx)*mxy)%mod << endl;
    return (1LL*st.query(0,mx)*mxy)%mod;
}

int init(int N, int X[], int Y[]) {
    x=X;
    y=Y;
    n=N;
    st = segTree<long long>(x,n);
    stmax = segTreeMax<long long>(y,n);
    pair<int,int>rg={-1,-1};
    for(int i = 0;i<n;i++){
        if(x[i]==1){
            if(rg.first==-1){
                rg.first=i;
                rg.second=i;
            }
            else{
                rg.second=i;
            }
        }
        else {
            if(rg.first!=-1)
                ones.insert(rg);
            rg={-1,-1};
        }
    }
    if(rg.first!=-1){
        ones.insert(rg);
    }
    //cout << "here" << endl;
    for(pair<int,int>p:ones){
        //cout << p.first << " " << p.second << endl;
    }
    return finans();
}


int updateX(int pos, int val) {
    if(x[pos]==1&&val!=1){
        set<pair<int,int>>::iterator it = ones.upper_bound({pos,2e9});
        pair<int,int>p = *(--it);
        ones.erase(p);
        if(p.first!=pos){
            ones.insert({p.first,pos-1});
        }
        if(p.second!=pos){
            ones.insert({pos+1,p.second});
        }
    }
    else if(x[pos]!=1&&val==1){
        if(ones.size()==0){
            ones.insert({pos,pos});
        }
        else{
            set<pair<int,int>>::iterator it = ones.upper_bound({pos,2e9});
            pair<int,int>p={0,0};
            if(it!=ones.begin()){
                p = *(--it);
                if(p.second==pos-1){
                    ones.erase(p);
                    ones.insert({p.first,pos});
                }
                else{
                    ones.insert({pos,pos});
                }
            }
            else{
                ones.insert({pos,pos});
            }
            it=ones.upper_bound({pos,2e9});
            if(it!=ones.end()){
                p=*(it);
                if(p.first==pos+1){
                    pair<int,int>p2=*(--it);
                    ones.erase(p);
                    ones.erase(p2);
                    ones.insert({p2.first,p.second});
                }
            }
        }
    }
    x[pos]=val;
    st.update(pos,val);
    //cout << "updated: " << endl;
    for(pair<int,int>p:ones){
        //cout << p.first << " " << p.second << endl;
    }
	return finans();
}

int updateY(int pos, int val) {
    y[pos]=val;
    stmax.update(pos,val);
	return finans();
}

Compilation message

horses.cpp: In constructor 'segTree<T>::segTree(int*, int)':
horses.cpp:31:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   31 |             int x = (int)pow(2,ceil(log2(siz)));
      |                 ^
horses.cpp:6:6: note: shadowed declaration is here
    6 | int *x;
      |      ^
horses.cpp: In constructor 'segTreeMax<T>::segTreeMax(int*, int)':
horses.cpp:93:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   93 |             int x = (int)pow(2,ceil(log2(siz)));
      |                 ^
horses.cpp:6:6: note: shadowed declaration is here
    6 | int *x;
      |      ^
horses.cpp: In function 'int finans()':
horses.cpp:156:25: warning: declaration of 'i' shadows a previous local [-Wshadow]
  156 |                 for(int i = (*it).first;i<=(*it).second;i++){
      |                         ^
horses.cpp:151:13: note: shadowed declaration is here
  151 |     for(int i = n-1;i>=0;i--){
      |             ^
horses.cpp:161:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  161 |                 cury = stmax.query((*it).first,(*it).second);
      |                        ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:172:16: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  172 |             if(curr>=1e9){
      |                ^~~~
horses.cpp:184:12: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  184 |         if(curr>=1e9){
      |            ^~~~
horses.cpp:189:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  189 |     return (1LL*st.query(0,mx)*mxy)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:219:22: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  219 |     for(pair<int,int>p:ones){
      |                      ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:273:22: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  273 |     for(pair<int,int>p:ones){
      |                      ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 0 ms 336 KB Output is correct
14 Correct 1 ms 504 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 504 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 0 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 504 KB Output is correct
32 Correct 1 ms 336 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 21660 KB Output is correct
2 Correct 85 ms 21576 KB Output is correct
3 Correct 56 ms 21588 KB Output is correct
4 Correct 74 ms 21576 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 508 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 476 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 404 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 30 ms 20740 KB Output is correct
34 Correct 27 ms 20780 KB Output is correct
35 Correct 49 ms 20820 KB Output is correct
36 Correct 47 ms 20816 KB Output is correct
37 Correct 42 ms 20808 KB Output is correct
38 Correct 66 ms 32608 KB Output is correct
39 Correct 27 ms 20816 KB Output is correct
40 Correct 37 ms 26696 KB Output is correct
41 Correct 22 ms 23032 KB Output is correct
42 Correct 23 ms 22864 KB Output is correct
43 Correct 34 ms 26924 KB Output is correct
44 Correct 34 ms 27104 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 1 ms 504 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 476 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 67 ms 21576 KB Output is correct
34 Correct 85 ms 21576 KB Output is correct
35 Correct 58 ms 21712 KB Output is correct
36 Correct 67 ms 21576 KB Output is correct
37 Correct 32 ms 20932 KB Output is correct
38 Correct 28 ms 20816 KB Output is correct
39 Correct 52 ms 20808 KB Output is correct
40 Correct 51 ms 20808 KB Output is correct
41 Correct 46 ms 20964 KB Output is correct
42 Correct 77 ms 32584 KB Output is correct
43 Correct 26 ms 21840 KB Output is correct
44 Correct 38 ms 26696 KB Output is correct
45 Correct 24 ms 22788 KB Output is correct
46 Correct 25 ms 22864 KB Output is correct
47 Correct 37 ms 26952 KB Output is correct
48 Correct 34 ms 26960 KB Output is correct
49 Correct 119 ms 28016 KB Output is correct
50 Correct 93 ms 27720 KB Output is correct
51 Correct 108 ms 33352 KB Output is correct
52 Correct 84 ms 33108 KB Output is correct
53 Correct 194 ms 25928 KB Output is correct
54 Correct 123 ms 37192 KB Output is correct
55 Correct 77 ms 23684 KB Output is correct
56 Correct 79 ms 28492 KB Output is correct
57 Correct 66 ms 24392 KB Output is correct
58 Correct 84 ms 24912 KB Output is correct
59 Correct 37 ms 26952 KB Output is correct