제출 #726035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726035		TheSahib	말 (IOI15_horses)	C++17	100 / 100	196 ms	38092 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, ll>

using namespace std;

const int MOD = 1e9 + 7;
const ll oo = 1e9 + 9;
const int MAX = 5e5 + 5;

struct DATA{
    int index, leftMultipliyer, rightMultiplier;
};

int n;
int price[MAX], cnt[MAX];
DATA tree[MAX * 4];


DATA merge(DATA a, DATA b){
    ll m = min(oo, 1ll * a.rightMultiplier * b.leftMultipliyer);
    if(price[a.index] / m >= price[b.index]){
        return {a.index, a.leftMultipliyer, min(oo, m * b.rightMultiplier)};
    }
    else{
        return {b.index, min(oo, m * a.leftMultipliyer), b.rightMultiplier};
    }
}

void build(int node, int l, int r){
    if(l == r){
        tree[node] = {l, cnt[l], 1};
        return;
    }

    int mid = (l + r) / 2;
    build(node << 1 | 1, l, mid);
    build((node + 1) << 1, mid + 1, r);

    tree[node] = merge(tree[(node << 1) | 1], tree[(node + 1) << 1]);
}

void update(int node, int l, int r, int pos, int val){
    if(l == r){
        tree[node] = {l, cnt[l], 1};
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid){
        update((node << 1) + 1, l, mid, pos, val);
    }
    else{
        update((node + 1) << 1, mid + 1, r, pos, val);
    }
    tree[node] = merge(tree[(node << 1) | 1], tree[(node + 1) << 1]);
}



int tree1[MAX * 4];

void build2(int node, int l, int r){
    if(l == r){
        tree1[node] = cnt[l];
        return;
    }
    int mid = (l + r) / 2;
    build2((node << 1) + 1, l, mid);
    build2((node + 1) << 1, mid + 1, r);
    tree1[node] = (1ll * tree1[(node << 1) + 1] * tree1[(node + 1) << 1]) % MOD;
}

void update2(int node, int l, int r, int pos, int val){
    if(l == r){
        tree1[node] = val;
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid){
        update2((node << 1) + 1, l, mid, pos, val);
    }
    else{
        update2((node + 1) << 1, mid + 1, r, pos, val);
    }
    tree1[node] = (1ll * tree1[(node << 1) + 1] * tree1[(node + 1) << 1]) % MOD;
}

int ask2(int node, int l, int r, int ql, int qr){
    if(qr < l || ql > r){
        return 1;
    }
    if(ql <= l && r <= qr){
        return tree1[node];
    }
    int mid = (l + r) / 2;
    return (1ll * ask2((node << 1) + 1, l, mid, ql, qr) * ask2((node + 1) << 1, mid + 1, r, ql, qr)) % MOD;
}

int calcAns(){
    DATA ans = tree[0];
    return 1ll * ask2(0, 0, n - 1, 0, ans.index) * price[ans.index] % MOD;
}


int init(int N, int X[], int Y[]) {
    n = N;
    for (int i = 0; i < n; i++)
    {
        cnt[i] = X[i];
        price[i] = Y[i];
    }
    build(0, 0, n - 1);
    build2(0, 0, n - 1);
    return calcAns();
}

int updateX(int pos, int val) {	
	cnt[pos] = val;
    update(0, 0, n - 1, pos, cnt[pos]);
    update2(0, 0, n - 1, pos, val);
    return calcAns();
}

int updateY(int pos, int val) {
	price[pos] = val;
    update(0, 0, n - 1, pos, cnt[pos]);
    return calcAns();
}

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

horses.cpp: In function 'DATA merge(DATA, DATA)':
horses.cpp:25:48: warning: narrowing conversion of '(long long int)std::min<long long int>(oo, (m * ((long long int)b.DATA::rightMultiplier)))' from 'long long int' to 'int' [-Wnarrowing]
   25 |         return {a.index, a.leftMultipliyer, min(oo, m * b.rightMultiplier)};
      |                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:25:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
horses.cpp:28:29: warning: narrowing conversion of '(long long int)std::min<long long int>(oo, (m * ((long long int)a.DATA::leftMultipliyer)))' from 'long long int' to 'int' [-Wnarrowing]
   28 |         return {b.index, min(oo, m * a.leftMultipliyer), b.rightMultiplier};
      |                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:28:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
horses.cpp: In function 'void build2(int, int, int)':
horses.cpp:72:75: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |     tree1[node] = (1ll * tree1[(node << 1) + 1] * tree1[(node + 1) << 1]) % MOD;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void update2(int, int, int, int, int)':
horses.cpp:87:75: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   87 |     tree1[node] = (1ll * tree1[(node << 1) + 1] * tree1[(node + 1) << 1]) % MOD;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int ask2(int, int, int, int, int)':
horses.cpp:98:102: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |     return (1ll * ask2((node << 1) + 1, l, mid, ql, qr) * ask2((node + 1) << 1, mid + 1, r, ql, qr)) % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int calcAns()':
horses.cpp:103:69: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |     return 1ll * ask2(0, 0, n - 1, 0, ans.index) * price[ans.index] % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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