oj.uz

Submission #568584

# Submission time Handle Problem Language Result Execution time Memory
568584 2022-05-25T17:53:46 Z n0sk1ll Horses (IOI15_horses) C++14
37 / 100
 733 ms 53220 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;
li mx[1111111],val[1111111];
int l[1111111],r[1111111];

li 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;
}

li 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));
}

li opti_mala()
{
    if (veci2.empty()) return Max(1,0,n-1);
    auto it=veci2.end();
    li tmp=1;
    vector<li> salim_se1;
    vector<li> salim_se2;
    vector<li> 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()%mod;
}

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()%mod;
}

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()%mod;
}

/*

3
2 1 3
3 4 1
1
2 1 2

*/

Compilation message

horses.cpp: In function 'li opti_mala()':
horses.cpp:7:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long 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:56: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {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:79:20: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   79 |  return opti_mala()%mod;
      |         ~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:94:20: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   94 |  return opti_mala()%mod;
      |         ~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:105:20: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
  105 |  return opti_mala()%mod;
      |         ~~~~~~~~~~~^~~~

Subtask #1
17.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 340 KB Output is correct
7 Correct 1 ms 340 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 212 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 212 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 340 KB Output is correct
20 Correct 0 ms 308 KB Output is correct

Subtask #2
0 / 17.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 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 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 224 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 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Incorrect 5 ms 320 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 52992 KB Output is correct
2 Correct 297 ms 53220 KB Output is correct
3 Correct 326 ms 53220 KB Output is correct
4 Correct 351 ms 53200 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 212 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 340 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 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 212 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 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Incorrect 5 ms 328 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 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 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 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 308 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 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 340 KB Output is correct
18 Correct 1 ms 292 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 448 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Incorrect 7 ms 324 KB Output isn't correct
28 Halted 0 ms 0 KB -