oj.uz

Submission #586826

# Submission time Handle Problem Language Result Execution time Memory
586826 2022-06-30T17:56:46 Z InternetPerson10 Horses (IOI15_horses) C++17
100 / 100
 572 ms 94384 KB 
#include "horses.h"
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll MOD = 1000000007;

vector<int> x, y;
set<int> nonOnes;

ll modpow(ll n, ll e = MOD - 2) {
    if(e == 0) return 1;
    ll g = modpow(n, e/2);
    g *= g;
    g %= MOD;
    if(e%2) {
        g *= n;
        g %= MOD;
    }
    return g;
}

struct SegTree {
    int lx, rx;
    int val = 0;
    SegTree *ls, *rs;
    SegTree(int l, int r) : lx(l), rx(r) {
        if(rx - lx != 1) {
            int mid = (lx + rx) / 2;
            ls = new SegTree(l, mid);
            rs = new SegTree(mid, r);
            val = max(ls->val, rs->val);
        }
        else {
            if(lx < (int)y.size()) val = y[lx];
        }
    }
    int getMax(int l, int r) {
        if(r <= lx || rx <= l) return 0;
        if(l <= lx && rx <= r) return val;
        return max(ls->getMax(l, r), rs->getMax(l, r));
    }
    int changeVal(int g) {
        if(g+1 <= lx || rx <= g) return val;
        if(g <= lx && rx <= g+1) return val = y[g];
        return val = max(ls->changeVal(g), rs->changeVal(g));
    }
};

ll prod = 1;
SegTree *st;

int recalc() {
    __int128 currProd = 1;
    auto it = nonOnes.end();
    int rightBorder = x.size();
    do {
        it--;
        int idx = *it;
        int val = x[idx];
        currProd *= val;
        if((currProd > 1000000001) || (it == nonOnes.begin())) {
            __int128 best = -1, base = (prod * modpow(currProd % MOD)) % MOD;
            auto it2 = nonOnes.end();
            do {
                it2--;
                best = max(best, currProd * st->getMax((*it2), rightBorder));
                rightBorder = (*it2);
                currProd /= x[(*it2)];
            } while(it2 != it);
            assert(currProd == 1);
            assert(best != -1);
            return (int)(((best % MOD) * (base % MOD)) % MOD);
        }
    } while(it != nonOnes.begin());
    assert(false);
}

int init(int n, int X[], int Y[]) {
    x.resize(n);
    y.resize(n);
    for(int i = 0; i < n; i++) {
        x[i] = X[i]; y[i] = Y[i];
    }
    // Process X
    nonOnes.insert(0);
    for(int i = 0; i < n; i++) {
        if(x[i] != 1) nonOnes.insert(i);
        prod *= x[i];
        prod %= MOD;
    }
    // Process Y
    int g = 1;
    while(g < n) g *= 2;
    st = new SegTree(0, g);
	return recalc();
}

int updateX(int pos, int val) {
    prod *= modpow(x[pos]);
    prod %= MOD;
    x[pos] = val;
    prod *= x[pos];
    prod %= MOD;
    if(pos) {
        nonOnes.erase(pos);
        if(val != 1) nonOnes.insert(pos);
    }
    return recalc();
}

int updateY(int pos, int val) {	
    y[pos] = val;
    st->changeVal(pos);
    return recalc();
}

Compilation message

horses.cpp: In function 'int recalc()':
horses.cpp:57:29: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   57 |     int rightBorder = x.size();
      |                       ~~~~~~^~
horses.cpp:64:64: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
   64 |             __int128 best = -1, base = (prod * modpow(currProd % MOD)) % 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 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 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 0 ms 224 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 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 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 1 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 0 ms 212 KB Output is correct
11 Correct 1 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 0 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 0 ms 212 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 1 ms 212 KB Output is correct
23 Correct 2 ms 436 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 3 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 81812 KB Output is correct
2 Correct 399 ms 81776 KB Output is correct
3 Correct 397 ms 85628 KB Output is correct
4 Correct 453 ms 89356 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 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 1 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 1 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 1 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 1 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 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 440 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 5 ms 440 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 3 ms 340 KB Output is correct
32 Correct 3 ms 340 KB Output is correct
33 Correct 92 ms 61416 KB Output is correct
34 Correct 82 ms 61436 KB Output is correct
35 Correct 236 ms 91808 KB Output is correct
36 Correct 229 ms 91728 KB Output is correct
37 Correct 113 ms 59636 KB Output is correct
38 Correct 142 ms 72356 KB Output is correct
39 Correct 80 ms 59436 KB Output is correct
40 Correct 188 ms 86996 KB Output is correct
41 Correct 102 ms 59488 KB Output is correct
42 Correct 149 ms 59468 KB Output is correct
43 Correct 230 ms 87232 KB Output is correct
44 Correct 198 ms 87236 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 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 1 ms 212 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 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 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 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3 ms 440 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 3 ms 340 KB Output is correct
33 Correct 572 ms 85648 KB Output is correct
34 Correct 407 ms 94384 KB Output is correct
35 Correct 431 ms 85540 KB Output is correct
36 Correct 427 ms 89520 KB Output is correct
37 Correct 101 ms 61516 KB Output is correct
38 Correct 85 ms 61476 KB Output is correct
39 Correct 222 ms 91744 KB Output is correct
40 Correct 217 ms 91652 KB Output is correct
41 Correct 109 ms 59652 KB Output is correct
42 Correct 128 ms 72420 KB Output is correct
43 Correct 81 ms 59392 KB Output is correct
44 Correct 210 ms 86860 KB Output is correct
45 Correct 80 ms 59412 KB Output is correct
46 Correct 89 ms 59536 KB Output is correct
47 Correct 210 ms 87344 KB Output is correct
48 Correct 203 ms 87232 KB Output is correct
49 Correct 225 ms 64440 KB Output is correct
50 Correct 206 ms 64452 KB Output is correct
51 Correct 378 ms 93740 KB Output is correct
52 Correct 294 ms 93112 KB Output is correct
53 Correct 553 ms 62736 KB Output is correct
54 Correct 285 ms 76364 KB Output is correct
55 Correct 175 ms 60412 KB Output is correct
56 Correct 311 ms 88652 KB Output is correct
57 Correct 316 ms 61096 KB Output is correct
58 Correct 418 ms 61640 KB Output is correct
59 Correct 202 ms 87224 KB Output is correct