oj.uz

답안 #586818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586818 2022-06-30T17:52:34 Z InternetPerson10 말 (IOI15_horses) C++17
17 / 100
 508 ms 94416 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;
            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:55: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
   64 |             __int128 best = -1, base = (prod * modpow(currProd)) % MOD;
      |                                                       ^~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 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 0 ms 212 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
12 Correct 1 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 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 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 0 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 1 ms 212 KB Output is correct
10 Correct 1 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 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 0 ms 212 KB Output is correct
18 Correct 0 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 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 508 ms 81836 KB Output is correct
2 Incorrect 376 ms 94416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 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 0 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 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 0 ms 212 KB Output is correct
14 Correct 1 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 0 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 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 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 1 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 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 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 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 0 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 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -