Submission #393191

#	Time	Username	Problem	Language	Result	Execution time	Memory
393191		ly20	Horses (IOI15_horses)	C++17	0 / 100	552 ms	47276 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];
long long 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) {
    if(ini == fim) {
        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);
}
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, 0, i, log2(x[i]));
        update(1, 0, n - 1, i, i, log2(y[i]));
        update2(1, 0, n - 1, i, x[i]);
    }
    int id = segl[0].second;
    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, 0, pos, 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);
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:65:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   65 |         update2(1, 0, n - 1, i, x[i]);
      |                                 ~~~^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:74:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |     update2(1, 0, n - 1, pos, vl);
      |                               ^~

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