oj.uz

Submission #1098298

# Submission time Handle Problem Language Result Execution time Memory
1098298 2024-10-09T08:43:16 Z alexander707070 Horses (IOI15_horses) C++14
54 / 100
 1500 ms 50260 KB 
#include<bits/stdc++.h>
#include "horses.h"

#define MAXN 500007
using namespace std;

const long long mod=1e9+7;

struct ST{
    int tree[4*MAXN];
    long long mult[4*MAXN];

    void update(int v,int l,int r,int pos,int val){
        if(l==r){
            tree[v]=val;
            mult[v]=val;
        }else{
            int tt=(l+r)/2;
            if(pos<=tt)update(2*v,l,tt,pos,val);
            else update(2*v+1,tt+1,r,pos,val);

            tree[v]=max(tree[2*v],tree[2*v+1]);
            mult[v]=(mult[2*v]*mult[2*v+1])%mod;
        }
    }

    int getmax(int v,int l,int r,int ll,int rr){
        if(ll>rr)return 0;
        if(l==ll and r==rr){
            return tree[v];
        }else{
            int tt=(l+r)/2;
            return max( getmax(2*v,l,tt,ll,min(tt,rr)) , getmax(2*v+1,tt+1,r,max(tt+1,ll),rr) );
        }
    }

    int solve(int v,int l,int r){
        if(l==r)return l;
        int tt=(l+r)/2;

        if(tree[2*v+1]>1)return solve(2*v+1,tt+1,r);
        return solve(2*v,l,tt);
    }

    int findpos(int v,int l,int r,int ll,int rr){
        if(ll>rr)return 0;
        if(l==ll and r==rr){
            if(tree[v]>1)return solve(v,l,r);
            return 0;
        }else{
            int tt=(l+r)/2;

            int curr=findpos(2*v+1,tt+1,r,max(tt+1,ll),rr);
            if(curr!=0)return curr;

            return findpos(2*v,l,tt,ll,min(tt,rr));
        }
    }

    long long getmult(int v,int l,int r,int ll,int rr){
        if(ll>rr)return 1;
        if(l==ll and r==rr)return mult[v];

        int tt=(l+r)/2;
        return (getmult(2*v,l,tt,ll,min(tt,rr)) * getmult(2*v+1,tt+1,r,max(tt+1,ll),rr))%mod;
    }
}xs,ys;

int n;
long long x[MAXN],y[MAXN];

int calc(){
    
    long long mult=1,res=0,ans=0;
    int to=n+1;

    vector< pair<int,int> > w;

    /*while(to>1 and mult<mod){
        int s=xs.findpos(1,1,n,1,to-1);
        if(s==0){
            w.push_back({1,to-1}); break;
        }else{
            w.push_back({s,to-1}); to=s;
            mult*=x[s];
        }
    }*/
   
    for(int i=n;i>=1;i--){
        mult*=x[i];

        if(x[i]!=1 or i==1){
            w.push_back({i,to-1});
            to=i;
        }

        if(mult>mod)break;
    }

    mult=1;
    for(int i=w.size()-1;i>=0;i--){
        long long curr=(long long) mult*ys.getmax(1,1,n,w[i].first,w[i].second);

        if(curr>res){
            res=curr;
            ans=((res%mod)*xs.getmult(1,1,n,1,w.back().first))%mod;
        }

        if(i>0)mult*=x[w[i-1].first];
    }

    return ans;
}

int init(int N, int X[], int Y[]) {
//int init(int N, vector<int> X, vector<int> Y) {

	n=N;
    for(int i=1;i<=n;i++){
        x[i]=X[i-1]; y[i]=Y[i-1];

        xs.update(1,1,n,i,x[i]);
        ys.update(1,1,n,i,y[i]);
    }

    return calc();
}

int updateX(int pos, int val) {	
	x[pos+1]=val;
    xs.update(1,1,n,pos+1,val);

    return calc();
}

int updateY(int pos, int val) {
	y[pos+1]=val;
    ys.update(1,1,n,pos+1,val);

    return calc();
}

/*int main(){

    init(3,{2,1,3},{3,4,1});
    cout<<updateY(1,2)<<"\n";

    return 0;
}*/

Compilation message

horses.cpp: In function 'int calc()':
horses.cpp:101:23: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  101 |     for(int i=w.size()-1;i>=0;i--){
      |               ~~~~~~~~^~
horses.cpp:112:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |     return ans;
      |            ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:122:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |         xs.update(1,1,n,i,x[i]);
      |                           ~~~^
horses.cpp:123:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  123 |         ys.update(1,1,n,i,y[i]);
      |                           ~~~^

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 37788 KB Output is correct
2 Correct 276 ms 50256 KB Output is correct
3 Correct 282 ms 41556 KB Output is correct
4 Correct 306 ms 45392 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 444 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 448 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 484 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 3 ms 348 KB Output is correct
28 Correct 2 ms 348 KB Output is correct
29 Correct 2 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 3 ms 348 KB Output is correct
33 Correct 184 ms 40732 KB Output is correct
34 Correct 154 ms 40708 KB Output is correct
35 Correct 183 ms 47604 KB Output is correct
36 Correct 178 ms 47700 KB Output is correct
37 Correct 414 ms 38992 KB Output is correct
38 Correct 162 ms 39764 KB Output is correct
39 Execution timed out 1567 ms 38732 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 3 ms 464 KB Output is correct
28 Correct 2 ms 348 KB Output is correct
29 Correct 2 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 3 ms 348 KB Output is correct
32 Correct 3 ms 348 KB Output is correct
33 Correct 393 ms 41580 KB Output is correct
34 Correct 254 ms 50260 KB Output is correct
35 Correct 302 ms 41844 KB Output is correct
36 Correct 298 ms 45392 KB Output is correct
37 Correct 190 ms 40784 KB Output is correct
38 Correct 157 ms 40788 KB Output is correct
39 Correct 180 ms 47696 KB Output is correct
40 Correct 177 ms 47576 KB Output is correct
41 Correct 407 ms 39184 KB Output is correct
42 Correct 162 ms 39816 KB Output is correct
43 Execution timed out 1516 ms 38888 KB Time limit exceeded
44 Halted 0 ms 0 KB -