제출 #586829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586829		InternetPerson10	말 (IOI15_horses)	C++11	100 / 100	555 ms	81912 KiB

horses

#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();
}

컴파일 시 표준 에러 (stderr) 메시지

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