제출 #653664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653664		esomer	말 (IOI15_horses)	C++17	100 / 100	775 ms	40944 KiB

horses

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

const ll MOD = 1e9 + 7;
const int maxN = 500000;
const int siz = 1048576 / 2;
int N;
int x[maxN];
int y[maxN];
int segTree[siz * 2];
int segTree2[siz * 2];
set<int> s;

void st(int i, int v, int p, int lx, int rx){
    if(rx - lx == 1){
        segTree[p] = v;
        return;
    }
    int m = (lx + rx) / 2;
    if(i < m) st(i, v, 2 * p + 1, lx, m);
    else st(i, v, 2 * p + 2, m, rx);
    segTree[p] = max(segTree[2 * p + 1], segTree[2 * p + 2]);
}

int mx(int l, int r, int p, int lx, int rx){
    if(lx >= l && rx <= r) return segTree[p];
    else if(lx >= r || rx <= l) return 0;
    int m = (lx + rx) / 2;
    int m1 = mx(l, r, 2 * p + 1, lx, m);
    int m2 = mx(l, r, 2 * p + 2, m, rx);
    return max(m1, m2);
}

void st_x(int i, int v, int p, int lx, int rx){
    if(rx - lx == 1){
        segTree2[p] = v;
        return;
    }
    int m = (lx + rx) / 2;
    if(i < m) st_x(i, v, 2 * p + 1, lx, m);
    else st_x(i, v, 2 * p + 2, m, rx);
    ll left = segTree2[2 * p + 1];
    ll right = segTree2[2 * p + 2];
    segTree2[p] = (left * right) % MOD;
}

ll mult(int l, int r, int p, int lx, int rx){
    if(lx >= l && rx <= r) return segTree2[p];
    else if(lx >= r || rx <= l) return 1;
    int m = (lx + rx) / 2;
    ll m1 = mult(l, r, 2 * p + 1, lx, m);
    ll m2 = mult(l, r, 2 * p + 2, m, rx);
    return (m1 * m2) % MOD;
}

int ans(){
    vector<int> ind;
    ll best = 0;
    ll optimaly = -1;
    int r;
    if(s.empty() == false){
        auto it = s.end();
        it--;
        ll curr = 1;
        bool included = 0;
        int limit = 1000000000;
        while(curr <= limit){
            curr *= x[*it];
            ind.push_back(*it);
            if(curr > limit) continue;
            if(*it == 0) included = 1;
            if(it != s.begin()) it--;
            else{
                if(*it != 0) ind.push_back(0);
                break;
            }
        }
        reverse(ind.begin(), ind.end());
        curr = 1;
        if(included) curr = x[0];
        ind.push_back(N);
        for(int i = 1; i < (int)ind.size(); i++){
            ll bestY = mx(ind[i - 1], ind[i], 0, 0, siz);
            if(best < curr * bestY){
                optimaly = bestY;
                best = curr * bestY;
                r = i;
            }
            curr *= x[ind[i]];
        }
    }else{
        ind.push_back(N);
        r = 0;
        optimaly = mx(0, N, 0, 0, siz);
    }
	return (optimaly * mult(0, ind[r], 0, 0, siz)) % MOD;
}

int init(int n, int X[], int Y[]) {
    N = n;
    for(int i = 0; i < siz; i++){
        segTree[i] = 0; segTree2[i] = 1;
    }
    for(int i = 0; i < N; i++){
        x[i] = X[i]; y[i] = Y[i];
        st(i, y[i], 0, 0, siz);
        st_x(i, x[i], 0, 0, siz);
        if(x[i] != 1) s.insert(i);
    }
    return ans();
}

int updateX(int pos, int val) {
    st_x(pos, val, 0, 0, siz);
    if(x[pos] != 1 && val == 1) s.erase(pos);
    else if(x[pos] == 1 && val != 1) s.insert(pos);
    x[pos] = val;
	return ans();
}

int updateY(int pos, int val) {
    st(pos, val, 0, 0, siz);
	return ans();
}

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

horses.cpp: In function 'void st_x(int, int, int, int, int)':
horses.cpp:48:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   48 |     segTree2[p] = (left * right) % MOD;
      |                   ~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int ans()':
horses.cpp:100:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  100 |  return (optimaly * mult(0, ind[r], 0, 0, siz)) % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:100:34: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |  return (optimaly * mult(0, ind[r], 0, 0, siz)) % MOD;
      |                                  ^

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23