oj.uz

Submission #568599

# Submission time Handle Problem Language Result Execution time Memory
568599 2022-05-25T19:13:51 Z n0sk1ll Horses (IOI15_horses) C++14
37 / 100
 730 ms 45636 KB 
#include "horses.h"

#include <bits/stdc++.h>

#define xx first
#define yy second
#define ff(i,a,b) for (int i=a;i<b;i++)
#define fff(i,a,b) for (int i=a;i<=b;i++)
#define bff(i,a,b) for (int i=b-1;i>=a;i--)
#define bfff(i,a,b) for (int i=b;i>=a;i--)

using namespace std;
long long int typedef li;
const int mod=1000000007;

set<int> veci2;

int k=1,n;
int mx[1111111],val[1111111];
int l[1111111],r[1111111];

int Pro(int p, int ll, int rr)
{
    if (ll>r[p] || rr<l[p]) return 1;
    if (ll<=l[p] && rr>=r[p]) return val[p];
    return (li)Pro(2*p,ll,rr)*Pro(2*p+1,ll,rr)%mod;
}

int Max(int p, int ll, int rr)
{
    if (ll>r[p] || rr<l[p]) return 0;
    if (ll<=l[p] && rr>=r[p]) return mx[p];
    return max(Max(2*p,ll,rr),Max(2*p+1,ll,rr));
}

int opti_mala()
{
    if (veci2.empty()) return Max(1,0,n-1);
    auto it=veci2.end();
    li tmp=1;
    vector<int> salim_se1;
    vector<int> salim_se2;
    vector<int> salim_se_ind;
    while (true)
    {
        --it;

        salim_se1.push_back(tmp);
        salim_se2.push_back(Max(1,*it,n-1));
        salim_se_ind.push_back(*it);

        tmp*=val[*it+k];
        if (tmp>mod) break;
        if (it==veci2.begin()) break;
    }

    reverse(salim_se1.begin(),salim_se1.end());
    reverse(salim_se2.begin(),salim_se2.end());
    reverse(salim_se_ind.begin(),salim_se_ind.end());

    int opt=0;
    ff(i,1,salim_se1.size()) if ((li)salim_se1[opt]*salim_se2[i]>(li)salim_se1[i]*salim_se2[opt]) opt=i;
    //cout<<"opt: "<<salim_se_ind[opt]<<endl;
    return (li)salim_se2[opt]*Pro(1,0,salim_se_ind[opt])%mod;
}

int init(int N, int X[], int Y[])
{
    n=N;
    while (k<n) k*=2;
    ff(i,0,k) l[i+k]=i,r[i+k]=i;
    bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
    ff(i,0,n) mx[i+k]=Y[i],val[i+k]=X[i];
    bff(i,1,k) mx[i]=max(mx[2*i],mx[2*i+1]);
    bff(i,1,k) val[i]=(li)val[2*i]*val[2*i+1]%mod;

    ff(i,0,n) if (X[i]>1) veci2.insert(i);

	return opti_mala();
}

int updateX(int p, int x)
{
	p+=k;
	//if (val[p]>=2 && x==1) veci2.erase(p-k);
	//if (val[p]==1 && x>=2) veci2.insert(p-k);
	val[p]=x,p>>=1;

	while (p)
    {
        val[p]=(li)val[2*p]*val[2*p+1]%mod;
        p>>=1;
    }
	return opti_mala();
}

int updateY(int p, int x)
{
	p+=k,mx[p]=x,p>>=1;
	while (p)
    {
        mx[p]=max(mx[2*p],mx[2*p+1]);
        p>>=1;
    }
	return opti_mala();
}

/*

3
2 1 3
3 4 1
1
2 1 2

*/

Compilation message

horses.cpp: In function 'int Pro(int, int, int)':
horses.cpp:26:47: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   26 |     return (li)Pro(2*p,ll,rr)*Pro(2*p+1,ll,rr)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int opti_mala()':
horses.cpp:48:29: warning: conversion from 'li' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   48 |         salim_se1.push_back(tmp);
      |                             ^~~
horses.cpp:7:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define ff(i,a,b) for (int i=a;i<b;i++)
......
   62 |     ff(i,1,salim_se1.size()) if ((li)salim_se1[opt]*salim_se2[i]>(li)salim_se1[i]*salim_se2[opt]) opt=i;
      |        ~~~~~~~~~~~~~~~~~~~~      
horses.cpp:62:5: note: in expansion of macro 'ff'
   62 |     ff(i,1,salim_se1.size()) if ((li)salim_se1[opt]*salim_se2[i]>(li)salim_se1[i]*salim_se2[opt]) opt=i;
      |     ^~
horses.cpp:64:57: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   64 |     return (li)salim_se2[opt]*Pro(1,0,salim_se_ind[opt])%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:75:46: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   75 |     bff(i,1,k) val[i]=(li)val[2*i]*val[2*i+1]%mod;
      |                       ~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:91:39: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |         val[p]=(li)val[2*p]*val[2*p+1]%mod;
      |                ~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 45364 KB Output is correct
2 Correct 261 ms 45588 KB Output is correct
3 Correct 285 ms 45552 KB Output is correct
4 Correct 322 ms 45636 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 264 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 308 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -