제출 #393194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393194		ly20	말 (IOI15_horses)	C++17	17 / 100	565 ms	41064 KiB

horses

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 512345, MOD = 1e9 + 7;
long long seg[4 * MAXN];
pair <double, int> segl[4 * MAXN];
double lz[4 * MAXN];
int x[MAXN], y[MAXN];
int n;
void refresh(int cur, int ini, int fim) {
    if(lz[cur] == 0) return;
    double temp = lz[cur];
    segl[cur].first += temp;
    lz[cur] = 0;
    if(ini == fim) return;
    int e = 2 * cur, d = 2 * cur + 1;
    lz[e] += temp; lz[d] += temp;
}
void update(int cur, int ini, int fim, int a, int b, double val) {
    if(ini > b || fim < a) return;
    refresh(cur, ini, fim);
    if(ini >= a &&  fim <= b) {
        lz[cur] += val;
        refresh(cur, ini, fim);
        return;
    }
    int m = (ini + fim) / 2;
    int e = 2 * cur, d = 2 * cur + 1;
    update(e, ini, m, a, b, val); update(d, m + 1, fim, a, b, val);
    segl[cur] = max(segl[e], segl[d]);
}
void update2(int cur, int ini, int fim, int id, int val) {
    if(ini > id || fim < id) return;
    if(ini == fim) {
        seg[cur] = val;
        return;
    }
    int m = (ini + fim) / 2;
    int e = 2 * cur, d = 2 * cur + 1;
    update2(e, ini, m, id, val); update2(d, m + 1, fim, id, val);
    seg[cur] = (seg[e] * seg[d]) % MOD;
}
long long query(int cur, int ini, int fim, int a, int b) {
    if(ini > b || fim < a) return 1;
    if(ini >= a && fim <= b) return seg[cur];
    int m = (ini + fim) / 2;
    int e = 2 * cur, d = 2 * cur + 1;
    return (query(e, ini, m, a, b) * query(d, m + 1, fim, a, b)) % MOD;
}
void build(int cur, int ini, int fim) {
    refresh(cur, ini, fim);
    //segl[cur].second = ini;
    if(ini == fim) {
        //cout << ini << " " << segl[cur].first << endl;
        segl[cur].second = ini;
        return;
    }
    int m = (ini + fim) / 2;
    int e = 2 * cur, d = 2 * cur + 1;
    build(e, ini, m); build(d, m + 1, fim);
    segl[cur] = max(segl[e], segl[d]);
}
int init(int N, int X[], int Y[]) {
    n = N;
    build(1, 0, n - 1);
    for(int i = 0; i < n; i++) {
        x[i] = X[i]; y[i] = Y[i];
        update(1, 0, n - 1, i, n - 1, log2(x[i]));
        update(1, 0, n - 1, i, i, log2(y[i]));
        update2(1, 0, n - 1, i, x[i]);
    }
    //build(1, 0, n - 1);
    int id = segl[1].second;
    //printf("%d %lf\n", id);
    long long resp = query(1, 0, n - 1, 0, id);
    resp = resp * y[id];
    return (int) (resp % MOD);
}
int updateX(int pos, int val) {
    long long vl = val;
    update2(1, 0, n - 1, pos, vl);
    update(1, 0, n - 1, pos, n - 1, log2(vl) - log2(x[pos]));
    x[pos] = vl;
    int id = segl[0].second;
    long long resp = query(1, 0, n - 1, 0, id);
    resp = resp * y[id];
    return (int) (resp % MOD);
}
int updateY(int pos, int val) {
    long long vl = val;
    update(1, 0, n - 1, pos, pos, log2(vl) - log2(y[pos]));
    y[pos] = vl;
    int id = segl[0].second;
    long long resp = query(1, 0, n - 1, 0, id);
    resp = resp * y[id];
    return (int) (resp % MOD);
}
/*int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &x[i]);
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &y[i]);
    }
    printf("%d\n", init(n, x, y));
    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        int tp, pos, val;
        scanf("%d %d %d", &tp, &pos, &val);
        if(tp == 1) printf("%d", updateX(pos, val));
        else printf("%d", updateY(pos, val));
    }
}*/

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

horses.cpp: In function 'int updateX(int, int)':
horses.cpp:80:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |     update2(1, 0, n - 1, pos, vl);
      |                               ^~
horses.cpp:82:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   82 |     x[pos] = vl;
      |              ^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:91:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |     y[pos] = vl;
      |              ^~

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