Submission #989053

#	Time	Username	Problem	Language	Result	Execution time	Memory
989053		crafticat	Horses (IOI15_horses)	C++17	100 / 100	655 ms	107564 KiB

horses

#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 (stderr)

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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23