oj.uz

Submission #653664

# Submission time Handle Problem Language Result Execution time Memory
653664 2022-10-27T15:14:33 Z esomer Horses (IOI15_horses) C++17
100 / 100
 775 ms 40944 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

const ll MOD = 1e9 + 7;
const int maxN = 500000;
const int siz = 1048576 / 2;
int N;
int x[maxN];
int y[maxN];
int segTree[siz * 2];
int segTree2[siz * 2];
set<int> s;

void st(int i, int v, int p, int lx, int rx){
    if(rx - lx == 1){
        segTree[p] = v;
        return;
    }
    int m = (lx + rx) / 2;
    if(i < m) st(i, v, 2 * p + 1, lx, m);
    else st(i, v, 2 * p + 2, m, rx);
    segTree[p] = max(segTree[2 * p + 1], segTree[2 * p + 2]);
}

int mx(int l, int r, int p, int lx, int rx){
    if(lx >= l && rx <= r) return segTree[p];
    else if(lx >= r || rx <= l) return 0;
    int m = (lx + rx) / 2;
    int m1 = mx(l, r, 2 * p + 1, lx, m);
    int m2 = mx(l, r, 2 * p + 2, m, rx);
    return max(m1, m2);
}

void st_x(int i, int v, int p, int lx, int rx){
    if(rx - lx == 1){
        segTree2[p] = v;
        return;
    }
    int m = (lx + rx) / 2;
    if(i < m) st_x(i, v, 2 * p + 1, lx, m);
    else st_x(i, v, 2 * p + 2, m, rx);
    ll left = segTree2[2 * p + 1];
    ll right = segTree2[2 * p + 2];
    segTree2[p] = (left * right) % MOD;
}

ll mult(int l, int r, int p, int lx, int rx){
    if(lx >= l && rx <= r) return segTree2[p];
    else if(lx >= r || rx <= l) return 1;
    int m = (lx + rx) / 2;
    ll m1 = mult(l, r, 2 * p + 1, lx, m);
    ll m2 = mult(l, r, 2 * p + 2, m, rx);
    return (m1 * m2) % MOD;
}

int ans(){
    vector<int> ind;
    ll best = 0;
    ll optimaly = -1;
    int r;
    if(s.empty() == false){
        auto it = s.end();
        it--;
        ll curr = 1;
        bool included = 0;
        int limit = 1000000000;
        while(curr <= limit){
            curr *= x[*it];
            ind.push_back(*it);
            if(curr > limit) continue;
            if(*it == 0) included = 1;
            if(it != s.begin()) it--;
            else{
                if(*it != 0) ind.push_back(0);
                break;
            }
        }
        reverse(ind.begin(), ind.end());
        curr = 1;
        if(included) curr = x[0];
        ind.push_back(N);
        for(int i = 1; i < (int)ind.size(); i++){
            ll bestY = mx(ind[i - 1], ind[i], 0, 0, siz);
            if(best < curr * bestY){
                optimaly = bestY;
                best = curr * bestY;
                r = i;
            }
            curr *= x[ind[i]];
        }
    }else{
        ind.push_back(N);
        r = 0;
        optimaly = mx(0, N, 0, 0, siz);
    }
	return (optimaly * mult(0, ind[r], 0, 0, siz)) % MOD;
}

int init(int n, int X[], int Y[]) {
    N = n;
    for(int i = 0; i < siz; i++){
        segTree[i] = 0; segTree2[i] = 1;
    }
    for(int i = 0; i < N; i++){
        x[i] = X[i]; y[i] = Y[i];
        st(i, y[i], 0, 0, siz);
        st_x(i, x[i], 0, 0, siz);
        if(x[i] != 1) s.insert(i);
    }
    return ans();
}

int updateX(int pos, int val) {
    st_x(pos, val, 0, 0, siz);
    if(x[pos] != 1 && val == 1) s.erase(pos);
    else if(x[pos] == 1 && val != 1) s.insert(pos);
    x[pos] = val;
	return ans();
}

int updateY(int pos, int val) {
    st(pos, val, 0, 0, siz);
	return ans();
}

Compilation message

horses.cpp: In function 'void st_x(int, int, int, int, int)':
horses.cpp:48:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   48 |     segTree2[p] = (left * right) % MOD;
      |                   ~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int ans()':
horses.cpp:100:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  100 |  return (optimaly * mult(0, ind[r], 0, 0, siz)) % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:100:34: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |  return (optimaly * mult(0, ind[r], 0, 0, siz)) % MOD;
      |                                  ^

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 40636 KB Output is correct
2 Correct 405 ms 40780 KB Output is correct
3 Correct 398 ms 40856 KB Output is correct
4 Correct 436 ms 40944 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 3 ms 4436 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 2 ms 4404 KB Output is correct
5 Correct 2 ms 4436 KB Output is correct
6 Correct 2 ms 4436 KB Output is correct
7 Correct 2 ms 4412 KB Output is correct
8 Correct 2 ms 4436 KB Output is correct
9 Correct 2 ms 4384 KB Output is correct
10 Correct 2 ms 4408 KB Output is correct
11 Correct 2 ms 4436 KB Output is correct
12 Correct 2 ms 4408 KB Output is correct
13 Correct 2 ms 4408 KB Output is correct
14 Correct 2 ms 4408 KB Output is correct
15 Correct 2 ms 4436 KB Output is correct
16 Correct 3 ms 4436 KB Output is correct
17 Correct 3 ms 4436 KB Output is correct
18 Correct 2 ms 4436 KB Output is correct
19 Correct 2 ms 4436 KB Output is correct
20 Correct 3 ms 4408 KB Output is correct
21 Correct 3 ms 4408 KB Output is correct
22 Correct 2 ms 4436 KB Output is correct
23 Correct 4 ms 4436 KB Output is correct
24 Correct 4 ms 4436 KB Output is correct
25 Correct 5 ms 4552 KB Output is correct
26 Correct 4 ms 4436 KB Output is correct
27 Correct 8 ms 4492 KB Output is correct
28 Correct 5 ms 4436 KB Output is correct
29 Correct 3 ms 4436 KB Output is correct
30 Correct 4 ms 4420 KB Output is correct
31 Correct 6 ms 4436 KB Output is correct
32 Correct 8 ms 4380 KB Output is correct
33 Correct 194 ms 16584 KB Output is correct
34 Correct 194 ms 16572 KB Output is correct
35 Correct 322 ms 39868 KB Output is correct
36 Correct 313 ms 39884 KB Output is correct
37 Correct 239 ms 16528 KB Output is correct
38 Correct 247 ms 28404 KB Output is correct
39 Correct 180 ms 16376 KB Output is correct
40 Correct 291 ms 39900 KB Output is correct
41 Correct 208 ms 16424 KB Output is correct
42 Correct 218 ms 16480 KB Output is correct
43 Correct 279 ms 39956 KB Output is correct
44 Correct 277 ms 39912 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 2 ms 4404 KB Output is correct
4 Correct 3 ms 4436 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 2 ms 4436 KB Output is correct
7 Correct 3 ms 4412 KB Output is correct
8 Correct 2 ms 4404 KB Output is correct
9 Correct 2 ms 4436 KB Output is correct
10 Correct 3 ms 4436 KB Output is correct
11 Correct 2 ms 4436 KB Output is correct
12 Correct 2 ms 4412 KB Output is correct
13 Correct 3 ms 4436 KB Output is correct
14 Correct 2 ms 4436 KB Output is correct
15 Correct 2 ms 4404 KB Output is correct
16 Correct 2 ms 4436 KB Output is correct
17 Correct 2 ms 4436 KB Output is correct
18 Correct 2 ms 4436 KB Output is correct
19 Correct 3 ms 4436 KB Output is correct
20 Correct 2 ms 4436 KB Output is correct
21 Correct 3 ms 4436 KB Output is correct
22 Correct 3 ms 4436 KB Output is correct
23 Correct 4 ms 4420 KB Output is correct
24 Correct 3 ms 4436 KB Output is correct
25 Correct 4 ms 4552 KB Output is correct
26 Correct 3 ms 4436 KB Output is correct
27 Correct 8 ms 4436 KB Output is correct
28 Correct 5 ms 4436 KB Output is correct
29 Correct 4 ms 4436 KB Output is correct
30 Correct 4 ms 4436 KB Output is correct
31 Correct 7 ms 4436 KB Output is correct
32 Correct 7 ms 4436 KB Output is correct
33 Correct 740 ms 40912 KB Output is correct
34 Correct 391 ms 40804 KB Output is correct
35 Correct 400 ms 40816 KB Output is correct
36 Correct 443 ms 40848 KB Output is correct
37 Correct 186 ms 16588 KB Output is correct
38 Correct 185 ms 16584 KB Output is correct
39 Correct 312 ms 40016 KB Output is correct
40 Correct 296 ms 39884 KB Output is correct
41 Correct 231 ms 16584 KB Output is correct
42 Correct 234 ms 28396 KB Output is correct
43 Correct 174 ms 16384 KB Output is correct
44 Correct 282 ms 39860 KB Output is correct
45 Correct 201 ms 16456 KB Output is correct
46 Correct 214 ms 16444 KB Output is correct
47 Correct 277 ms 39884 KB Output is correct
48 Correct 277 ms 39856 KB Output is correct
49 Correct 304 ms 18484 KB Output is correct
50 Correct 268 ms 18460 KB Output is correct
51 Correct 440 ms 40772 KB Output is correct
52 Correct 383 ms 40780 KB Output is correct
53 Correct 775 ms 18416 KB Output is correct
54 Correct 428 ms 31320 KB Output is correct
55 Correct 265 ms 16680 KB Output is correct
56 Correct 377 ms 40760 KB Output is correct
57 Correct 508 ms 17356 KB Output is correct
58 Correct 632 ms 17368 KB Output is correct
59 Correct 275 ms 39872 KB Output is correct