| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 568575 |
2022-05-25T17:37:00 Z |
n0sk1ll |
Horses (IOI15_horses) |
C++14 |
|
50 ms |
25228 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 (tmp/salim_se1[i]*salim_se2[i]>tmp/salim_se1[opt]*salim_se2[opt]) opt=i;
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;
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();
}
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 (tmp/salim_se1[i]*salim_se2[i]>tmp/salim_se1[opt]*salim_se2[opt]) opt=i;
| ~~~~~~~~~~~~~~~~~~~~
horses.cpp:62:5: note: in expansion of macro 'ff'
62 | ff(i,1,salim_se1.size()) if (tmp/salim_se1[i]*salim_se2[i]>tmp/salim_se1[opt]*salim_se2[opt]) opt=i;
| ^~
horses.cpp:63:57: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
63 | return (li)salim_se2[opt]*Pro(1,0,salim_se_ind[opt])%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:74:46: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
74 | 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:88:39: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
88 | val[p]=(li)val[2*p]*val[2*p+1]%mod;
| ~~~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
25228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
