oj.uz

Submission #568606

# Submission time Handle Problem Language Result Execution time Memory
568606 2022-05-25T19:21:07 Z n0sk1ll Horses (IOI15_horses) C++14
100 / 100
 767 ms 56688 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);
    veci2.insert(0);
    //ff(i,0,n) veci2.insert(i);

	return opti_mala();
}

int updateX(int p, int x)
{
	p+=k;
	if (x<=1 && p) veci2.erase(p-k);
	else 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:93:39: warning: conversion from 'li' {aka 'long long int'} to 'int' may change value [-Wconversion]
   93 |         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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 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 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 340 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 45032 KB Output is correct
2 Correct 312 ms 45036 KB Output is correct
3 Correct 326 ms 45052 KB Output is correct
4 Correct 396 ms 44988 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 360 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 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 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 5 ms 340 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 452 KB Output is correct
31 Correct 3 ms 324 KB Output is correct
32 Correct 4 ms 324 KB Output is correct
33 Correct 40 ms 20724 KB Output is correct
34 Correct 40 ms 24508 KB Output is correct
35 Correct 210 ms 54940 KB Output is correct
36 Correct 171 ms 54732 KB Output is correct
37 Correct 95 ms 22744 KB Output is correct
38 Correct 110 ms 35532 KB Output is correct
39 Correct 40 ms 22444 KB Output is correct
40 Correct 157 ms 49968 KB Output is correct
41 Correct 66 ms 22564 KB Output is correct
42 Correct 80 ms 22672 KB Output is correct
43 Correct 175 ms 50224 KB Output is correct
44 Correct 145 ms 50284 KB Output is correct

Subtask #5
23.0 / 23.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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 2 ms 428 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 3 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 452 KB Output is correct
31 Correct 4 ms 468 KB Output is correct
32 Correct 4 ms 340 KB Output is correct
33 Correct 699 ms 44940 KB Output is correct
34 Correct 299 ms 44968 KB Output is correct
35 Correct 326 ms 45068 KB Output is correct
36 Correct 400 ms 45060 KB Output is correct
37 Correct 44 ms 20812 KB Output is correct
38 Correct 43 ms 24536 KB Output is correct
39 Correct 189 ms 54920 KB Output is correct
40 Correct 173 ms 54764 KB Output is correct
41 Correct 106 ms 22768 KB Output is correct
42 Correct 108 ms 35480 KB Output is correct
43 Correct 32 ms 22476 KB Output is correct
44 Correct 156 ms 50016 KB Output is correct
45 Correct 62 ms 22560 KB Output is correct
46 Correct 77 ms 22540 KB Output is correct
47 Correct 160 ms 50300 KB Output is correct
48 Correct 156 ms 50296 KB Output is correct
49 Correct 213 ms 27556 KB Output is correct
50 Correct 153 ms 27592 KB Output is correct
51 Correct 353 ms 56688 KB Output is correct
52 Correct 280 ms 56200 KB Output is correct
53 Correct 767 ms 25940 KB Output is correct
54 Correct 357 ms 39396 KB Output is correct
55 Correct 139 ms 23612 KB Output is correct
56 Correct 272 ms 51724 KB Output is correct
57 Correct 491 ms 24152 KB Output is correct
58 Correct 608 ms 24692 KB Output is correct
59 Correct 156 ms 50232 KB Output is correct