oj.uz

답안 #653656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653656 2022-10-27T14:38:48 Z esomer 말 (IOI15_horses) C++17
0 / 100
 956 ms 40784 KB 
#include<bits/stdc++.h>
#include "horses.h"

using namespace std;

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

const ll MOD = 1e9 + 7;
const int maxN = 500000;
const int siz = 1048576;
int N;
int x[maxN];
int y[maxN];
int segTree[siz];
int segTree2[siz];
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[] /*vector<int> X, vector<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();
}

/*
int main() {
    int n; cin >> n;
    vector<int> v(n);
    vector<int> v2(n);
    for(auto &i : v) cin >> i;
    for(auto &i : v2) cin >> i;
    cout << init(n, v, v2) << endl;
    int m; cin >> m;
    while(m--){
        int t, pos, val; cin >> t >> pos >> val;
        if(t) cout << updateX(pos, val) << endl;
        else cout << updateY(pos, val)<< endl;
    }
}*/

Compilation message

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

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8404 KB Output is correct
2 Incorrect 4 ms 8416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8404 KB Output is correct
2 Incorrect 4 ms 8456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 956 ms 40784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8404 KB Output is correct
2 Incorrect 6 ms 8532 KB Output isn't correct
3 Halted 0 ms 0 KB -