oj.uz

Submission #1002551

# Submission time Handle Problem Language Result Execution time Memory
1002551 2024-06-19T16:05:31 Z Ausp3x Horses (IOI15_horses) C++17
17 / 100
 119 ms 29780 KB 
// 人外有人，天外有天
// author: Ausp3x
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "horses.h"
typedef long long             lng;
typedef unsigned int          uint;
typedef unsigned long long    ulng;
using namespace std;
using namespace __gnu_pbds;
 
int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;
 
int const MOD = 1000000007;

lng modPow(lng x, lng y) {
    lng res = 1;
 
    while (y > 0) {
        if (y & 1) {
            res *= x;
            res %= MOD;
        }
 
        y >>= 1;
        x *= x;
        x %= MOD;
    }
 
    return (res + MOD) % MOD;
}

int nextPowOf2(int n) {
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;

    return n;
}

int N;
vector<int> X, Y;

int N2;
// actual prod, modulo prod
vector<pair<lng, lng>> x_seg;  
vector<int> i_seg;

lng queryXSeg(int l, int r, int opt) {
    l += N2;
    r += N2;

    lng res = 1;
    if (opt == 1) {
        while (l <= r) {
            if (l & 1) {
                res *= x_seg[l++].first;
                if (res > INF32)
                    res = INF32;
            } 
            if (!(r & 1)) {
                res *= x_seg[r--].first;
                if (res > INF32)
                    res = INF32;
            }

            l >>= 1;
            r >>= 1;
        }
    } else if (opt == 2) {
        while (l <= r) {
            if (l & 1)
                (res *= x_seg[l++].second) %= MOD;
            if (~r & 1)
                (res *= x_seg[r--].second) %= MOD;

            l >>= 1;
            r >>= 1;
        }
    }

    return res;
}

void updateISeg(int i) {
    i = (i + N2) >> 1;
    while (i > 0) {
        if (i_seg[2 * i + 1] == -1)
            i_seg[i] = i_seg[2 * i];
        else {
            if (Y[i_seg[2 * i]] >= queryXSeg(i_seg[2 * i] + 1, i_seg[2 * i + 1], 1) * Y[i_seg[2 * i + 1]])
                i_seg[i] = i_seg[2 * i];
            else
                i_seg[i] = i_seg[2 * i + 1];
        }

        i >>= 1;
    }

    return;
}

int init(int n, int x[], int y[]) {
    N = n;
    X.clear();
    X.resize(N);
    Y.clear();
    Y.resize(N);
    for (int i = 0; i < N; i++) {
        X[i] = x[i];
        Y[i] = y[i];
    }
    
    N2 = nextPowOf2(N);
    x_seg.clear();
    x_seg.resize(2 * N2, {-1, -1});
    for (int i = N2; i < N2 + N; i++) {
        x_seg[i].first = X[i - N2];
        x_seg[i].second = X[i - N2];
    }
    for (int d = N2 / 2; d >= 1; d >>= 1)
        for (int i = d; i < 2 * d; i++) {
            if (x_seg[2 * i + 1].first == -1)
                x_seg[i] = x_seg[2 * i];
            else {
                x_seg[i].first = x_seg[2 * i].first * x_seg[2 * i + 1].first;
                if (x_seg[i].first > INF32)
                    x_seg[i].first = INF32;
                (x_seg[i].second = x_seg[2 * i].second * x_seg[2 * i + 1].second) %= MOD;
            }
        }
    
    // for (auto [x, y] : x_seg)
    //     cout << x << ' ';
    // cout << endl;
    // for (auto [x, y] : x_seg)
    //     cout << y << ' ';
    // cout << endl;
    
    i_seg.clear();
    i_seg.resize(2 * N2, -1);
    for (int i = N2; i < N2 + N; i++)
        i_seg[i] = i - N2;
    for (int d = N2 / 2; d >= 1; d >>= 1)
        for (int i = d; i < 2 * d; i++) {
            if (i_seg[2 * i + 1] == -1)
                i_seg[i] = i_seg[2 * i];
            else {
                if (Y[i_seg[2 * i]] >= queryXSeg(i_seg[2 * i] + 1, i_seg[2 * i + 1], 1) * Y[i_seg[2 * i + 1]])
                    i_seg[i] = i_seg[2 * i];
                else
                    i_seg[i] = i_seg[2 * i + 1];
            }
        }
    
    // for (int x : i_seg)
    //     cout << x << ' ';
    // cout << endl;

    return queryXSeg(0, i_seg[1], 2) * Y[i_seg[1]] % MOD;
}

int updateX(int i, int v) {
    i = i + N2;
    x_seg[i] = {v, v};
    i >>= 1;
    while (i > 0) {
        if (x_seg[2 * i + 1].first == -1)
            x_seg[i] = x_seg[2 * i];
        else {
            x_seg[i].first = x_seg[2 * i].first * x_seg[2 * i + 1].first;
            if (x_seg[i].first > INF32)
                x_seg[i].first = INF32;
            (x_seg[i].second = x_seg[2 * i].second * x_seg[2 * i + 1].second) %= MOD;
        }

        i >>= 1;
    }

    updateISeg(i);

    return queryXSeg(0, i_seg[1], 2) * Y[i_seg[1]] % MOD;
}

int updateY(int i, int v) {
    Y[i] = v;

    updateISeg(i);

    return queryXSeg(0, i_seg[1], 2) * Y[i_seg[1]] % MOD;
}

/*
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int x[3] = {2, 1, 3};
    int y[3] = {3, 4, 1};
    cout << init(3, x, y) << endl;
    cout << updateY(1, 2) << endl;

    return 0;
}
//*/

/*
lng almostAllHorses = 1;
int getMaxValue(int opt) {
    if (opt == 1) {
        lng horses = 1;
        for (int i = 0; i < N; i++) {
            (horses *= X[i]) %= MOD;
            
            bool chk = true;
            lng cur = 1; 
            for (int j = i + 1; j < N; j++) {
                if (cur == INF32 || cur * X[j] > INF32) {
                    chk = false;
                    break;
                }
                cur *= X[j];
 
                if (cur * Y[j] > Y[i]) {
                    chk = false;
                    break;
                }
            }
                
            if (chk) {
                return horses * Y[i] % MOD;
            }
        }
    } else if (opt == 2) {
        lng horses = almostAllHorses;
        for (int i = max(N - 64, 0); i < N; i++) {
            (horses *= X[i]) %= MOD;
            
            bool chk = true;
            lng cur = 1; 
            for (int j = i + 1; j < N; j++) {
                if (cur == INF32 || cur * X[j] > INF32) {
                    chk = false;
                    break;
                }
                cur *= X[j];
 
                if (cur * Y[j] > Y[i]) {
                    chk = false;
                    break;
                }
            }
                
            if (chk) {
                return horses * Y[i] % MOD;
            }
        }
    }
 
    return -1;
}
 
bool allXG1 = true;
int init(int n, int x[], int y[]) {
    N = n;
    X.resize(n);
    Y.resize(n);
    for (int i = 0; i < N; i++) {
        if (i < N - 64)
            (almostAllHorses *= x[i]) %= MOD;
        
        if (x[i] < 2)
            allXG1 = false;

        X[i] = x[i];
        Y[i] = y[i];
    }
 
	return (allXG1 ? getMaxValue(2) : getMaxValue(1));
}
 
bool allValG1 = true;
int updateX(int pos, int val) {
    if (pos < N - 64) {
        (almostAllHorses *= modPow(X[pos], MOD - 2)) %= MOD;
        (almostAllHorses *= val) %= MOD;
    }

    if (val < 2)
        allValG1 = false;
    
    X[pos] = val;

	return (allXG1 && allValG1 ? getMaxValue(2) : getMaxValue(1));
}
 
int updateY(int pos, int val) {    
    Y[pos] = val;
 
	return (allXG1 && allValG1 ? getMaxValue(2) : getMaxValue(1));
}
//*/

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:166:52: warning: conversion from 'lng' {aka 'long long int'} to 'int' may change value [-Wconversion]
  166 |     return queryXSeg(0, i_seg[1], 2) * Y[i_seg[1]] % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:188:52: warning: conversion from 'lng' {aka 'long long int'} to 'int' may change value [-Wconversion]
  188 |     return queryXSeg(0, i_seg[1], 2) * Y[i_seg[1]] % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:196:52: warning: conversion from 'lng' {aka 'long long int'} to 'int' may change value [-Wconversion]
  196 |     return queryXSeg(0, i_seg[1], 2) * Y[i_seg[1]] % 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 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 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 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 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 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 0 ms 348 KB Output is correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 29780 KB Output is correct
2 Correct 119 ms 29544 KB Output is correct
3 Correct 94 ms 29780 KB Output is correct
4 Incorrect 94 ms 29548 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 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 0 ms 348 KB Output is correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
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 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 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 0 ms 348 KB Output is correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -