oj.uz

Submission #989053

# Submission time Handle Problem Language Result Execution time Memory
989053 2024-05-27T11:08:53 Z crafticat Horses (IOI15_horses) C++17
100 / 100
 655 ms 107564 KB 
#include <bits/stdc++.h>

using namespace std;
constexpr int MOD = 1e9 + 7;
using ll = __int128;

vector<int> x, y;
set<int> exists;
ll global = 1;
int n;

ll myPOW(ll a, ll b) {
    if (b == 0) return 1;
    ll v = myPOW(a, b / 2);
    v *= v;
    v %= MOD;
    if (b % 2 == 1) v *= a;
    v %= MOD;
    return v;
}

ll inv(ll v) {
    return myPOW(v, MOD - 2);
}

struct Segment {
    Segment *left = nullptr, *right = nullptr;
    int l, r, mid;
    ll val = 1;

    Segment(int l, int r) : l(l), r(r), mid((r + l) / 2) {
        if (r - l > 1) {
            left = new Segment(l,mid);
            right = new Segment(mid,r);
        }
    }
    int q(int a, int b) {
        if (a >= r || b <= l) return 0;
        if (a <= l && b >= r) return val;

        return max(left->q(a,b), right->q(a,b));
    }
    void update(int pos, int u) {
        if (r - l <= 1) {
            val = u;
            return;
        }
        if (pos < mid)
            left->update(pos,u);
        else
            right->update(pos,u);
        val = max(left->val,right->val);
    }
};

Segment *seg;

int solve() {
    int cor = n - 1;
    ll mul = x[cor];
    stack<int> prop;
    prop.push(cor);

    while (mul < MOD) {
        auto it = exists.upper_bound(-cor);
        if (it == exists.end()) break;
        cor = -*it;
        mul *= x[cor];
        prop.push(cor);
    }
    if (cor > 0) {
        cor = 0;
        mul *= x[0];
        prop.push(0);
    }

    ll left = global * inv(mul % MOD) % MOD;
    ll ans = 0;

    mul = 1;
    while (!prop.empty()) {
        auto c = prop.top(); prop.pop();
        ans = max(ans, mul * seg->q(cor,c));
        mul *= x[c];
        ans = max(ans, y[c] * mul);
        cor = c;
    }
    ans %= MOD;
    return (ans * left) % MOD;
}

int init(int N, int X[], int Y[]) {
    n = N;
    x.resize(N);
    y.resize(N);
    seg = new Segment(0,N);
    for (int i = 0; i < N; ++i) {
        x[i] = X[i];
        y[i] = Y[i];
        global *= x[i];
        global %= MOD;
        if (x[i] != 1) {
            exists.insert(-i);
        } else
            seg->update(i,y[i]);
    }

    return solve();
}

int updateX(int pos, int val) {
    if (exists.count(-pos)) {
        exists.erase(-pos);
    } else seg->update(pos,0);

    global *= inv(x[pos]);
    global %= MOD;
    x[pos] = val;
    global *= x[pos];
    global %= MOD;
    if (x[pos] != 1) {
        exists.insert(-pos);
    } else seg->update(pos,y[pos]);
    return solve();
}
int updateY(int pos, int val) {
    y[pos] = val;
    if (!exists.count(pos)) seg->update(pos,y[pos]);
    return solve();
}
#if DEBUG
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int v; cin >> v;
    return v;
}


int main() {

	int N; N = _readInt();

	int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
	int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);

	for (int i = 0; i < N; i++) {
		X[i] = _readInt();
	}

	for (int i = 0; i < N; i++) {
		Y[i] = _readInt();
	}

	cout << init(N,X,Y) << endl;

	int M; M = _readInt();

	for (int i = 0; i < M; i++) {
		int type; type = _readInt();
		int pos; pos = _readInt();
		int val; val = _readInt();

		if (type == 1) {
			cout << updateX(pos,val) << endl;
		} else if (type == 2) {
            cout << updateY(pos,val) << endl;
		}
	}

	return 0;
}
#endif

Compilation message

horses.cpp: In constructor 'Segment::Segment(int, int)':
horses.cpp:31:24: warning: declaration of 'r' shadows a member of 'Segment' [-Wshadow]
   31 |     Segment(int l, int r) : l(l), r(r), mid((r + l) / 2) {
      |                    ~~~~^
horses.cpp:28:12: note: shadowed declaration is here
   28 |     int l, r, mid;
      |            ^
horses.cpp:31:17: warning: declaration of 'l' shadows a member of 'Segment' [-Wshadow]
   31 |     Segment(int l, int r) : l(l), r(r), mid((r + l) / 2) {
      |             ~~~~^
horses.cpp:28:9: note: shadowed declaration is here
   28 |     int l, r, mid;
      |         ^
horses.cpp: In constructor 'Segment::Segment(int, int)':
horses.cpp:31:24: warning: declaration of 'r' shadows a member of 'Segment' [-Wshadow]
   31 |     Segment(int l, int r) : l(l), r(r), mid((r + l) / 2) {
      |                    ~~~~^
horses.cpp:28:12: note: shadowed declaration is here
   28 |     int l, r, mid;
      |            ^
horses.cpp:31:17: warning: declaration of 'l' shadows a member of 'Segment' [-Wshadow]
   31 |     Segment(int l, int r) : l(l), r(r), mid((r + l) / 2) {
      |             ~~~~^
horses.cpp:28:9: note: shadowed declaration is here
   28 |     int l, r, mid;
      |         ^
horses.cpp: In constructor 'Segment::Segment(int, int)':
horses.cpp:31:24: warning: declaration of 'r' shadows a member of 'Segment' [-Wshadow]
   31 |     Segment(int l, int r) : l(l), r(r), mid((r + l) / 2) {
      |                    ~~~~^
horses.cpp:28:12: note: shadowed declaration is here
   28 |     int l, r, mid;
      |            ^
horses.cpp:31:17: warning: declaration of 'l' shadows a member of 'Segment' [-Wshadow]
   31 |     Segment(int l, int r) : l(l), r(r), mid((r + l) / 2) {
      |             ~~~~^
horses.cpp:28:9: note: shadowed declaration is here
   28 |     int l, r, mid;
      |         ^
horses.cpp: In member function 'int Segment::q(int, int)':
horses.cpp:39:38: warning: conversion from 'll' {aka '__int128'} to 'int' may change value [-Wconversion]
   39 |         if (a <= l && b >= r) return val;
      |                                      ^~~
horses.cpp: In function 'int solve()':
horses.cpp:89:25: warning: conversion from 'll' {aka '__int128'} to 'int' may change value [-Wconversion]
   89 |     return (ans * left) % MOD;
      |            ~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 95312 KB Output is correct
2 Correct 359 ms 95312 KB Output is correct
3 Correct 348 ms 95316 KB Output is correct
4 Correct 376 ms 95184 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 440 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 2 ms 604 KB Output is correct
28 Correct 2 ms 604 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 2 ms 604 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 2 ms 600 KB Output is correct
33 Correct 121 ms 74864 KB Output is correct
34 Correct 117 ms 74948 KB Output is correct
35 Correct 187 ms 104992 KB Output is correct
36 Correct 178 ms 105044 KB Output is correct
37 Correct 141 ms 73040 KB Output is correct
38 Correct 163 ms 86104 KB Output is correct
39 Correct 105 ms 72788 KB Output is correct
40 Correct 169 ms 100120 KB Output is correct
41 Correct 117 ms 72788 KB Output is correct
42 Correct 120 ms 73040 KB Output is correct
43 Correct 173 ms 100688 KB Output is correct
44 Correct 150 ms 100688 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 432 KB Output is correct
23 Correct 2 ms 452 KB Output is correct
24 Correct 3 ms 604 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 3 ms 600 KB Output is correct
28 Correct 2 ms 604 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 2 ms 604 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 2 ms 600 KB Output is correct
33 Correct 655 ms 99044 KB Output is correct
34 Correct 358 ms 107564 KB Output is correct
35 Correct 368 ms 99068 KB Output is correct
36 Correct 372 ms 102992 KB Output is correct
37 Correct 114 ms 74976 KB Output is correct
38 Correct 117 ms 74832 KB Output is correct
39 Correct 206 ms 105132 KB Output is correct
40 Correct 178 ms 105044 KB Output is correct
41 Correct 139 ms 73020 KB Output is correct
42 Correct 155 ms 85884 KB Output is correct
43 Correct 104 ms 72784 KB Output is correct
44 Correct 166 ms 100180 KB Output is correct
45 Correct 113 ms 72800 KB Output is correct
46 Correct 114 ms 72972 KB Output is correct
47 Correct 154 ms 100688 KB Output is correct
48 Correct 151 ms 100684 KB Output is correct
49 Correct 299 ms 78096 KB Output is correct
50 Correct 256 ms 77844 KB Output is correct
51 Correct 388 ms 106868 KB Output is correct
52 Correct 286 ms 106576 KB Output is correct
53 Correct 528 ms 76260 KB Output is correct
54 Correct 414 ms 89864 KB Output is correct
55 Correct 209 ms 73996 KB Output is correct
56 Correct 313 ms 101968 KB Output is correct
57 Correct 259 ms 74440 KB Output is correct
58 Correct 354 ms 74972 KB Output is correct
59 Correct 158 ms 100608 KB Output is correct