Submission #438366

#	Time	Username	Problem	Language	Result	Execution time	Memory
438366		illyakr	Horses (IOI15_horses)	C++14	54 / 100	1581 ms	32328 KiB

horses

#include <iostream>
#include <set>
#include "horses.h"
using namespace std;
#define ll long long
const long long mod = 1000000007;
const long long mx = 1000000018;

int n;
int x[501010], y[501010];
int t[2010101];
int Mxt[2010101];
set<int> Lf;
int Rf[501010];

void build(int v, int vl, int vr) {
    if (vl == vr) {
        t[v] = x[vl];
        Mxt[v] = vl;
        return;
    }
    int vm = (vl + vr) / 2;
    build(2 * v, vl, vm);
    build(2 * v + 1, vm + 1, vr);
    t[v] = ((ll)t[2 * v] * (ll)t[2 * v + 1]) % mod;

    if (y[Mxt[2 * v]] > y[Mxt[2 * v + 1]])
        Mxt[v] = Mxt[2 * v];
    else
        Mxt[v] = Mxt[2 * v + 1];
}
void upd(int v, int vl, int vr, int pos, int val) {
    if (vl == vr) {
        t[v] = val % mod;
        return;
    }
    int vm = (vl + vr) / 2;
    if (pos <= vm)upd(2 * v, vl, vm, pos, val);
    else upd(2 * v + 1, vm + 1, vr, pos, val);
    t[v] = ((ll)t[2 * v] * (ll)t[2 * v + 1]) % mod;
}
void Mxupd(int v, int vl, int vr, int pos) {
    if (vl == vr) {
        Mxt[v] = vl;
        return;
    }
    int vm = (vl + vr) / 2;
    if (pos <= vm)Mxupd(2 * v, vl, vm, pos);
    else Mxupd(2 * v + 1, vm + 1, vr, pos);
    if (y[Mxt[2 * v]] > y[Mxt[2 * v + 1]])
        Mxt[v] = Mxt[2 * v];
    else
        Mxt[v] = Mxt[2 * v + 1];
}
int gt(int v, int vl, int vr, int l, int r) {
    if (l <= vl && vr <= r)return t[v] % mod;
    if (r < vl || vr < l)return 1ll;
    int vm = (vl + vr) / 2;
    return ((ll)gt(2 * v, vl, vm, l, r) * (ll)gt(2 * v + 1, vm + 1, vr, l, r)) % mod;
}
int Mxgt(int v, int vl, int vr, int l, int r) {
    if (l <= vl && vr <= r)return Mxt[v];
    if (r < vl || vr < l)return -1;
    int vm = (vl + vr) / 2;
    int f = Mxgt(2 * v, vl, vm, l, r);
    int s = Mxgt(2 * v + 1, vm + 1, vr, l, r);
    if (f == -1)return s;
    if (s == -1)return f;
    if (y[f] < y[s])return s;
    return f;
}

set<int>::iterator Aps;
int gtspec(int i) {
    if (*Aps == 1010101010)--Aps;
    while (i < *Aps)--Aps;
    int NUM = *Aps;

    if (NUM == -1)return i - 1;
    if (NUM <= i && i <= Rf[NUM])return (NUM - 1);
    return i - 1;
}

int opp() {
    Aps = --Lf.end();
    int cnt = y[n - 1];
    int last = n - 1;
    for (int i = n - 1; i > 0;) {
        if (x[i] > mx / cnt)cnt = mx;
        else cnt *= x[i];
            if (cnt == mx)break;
        if (x[i] > 1) {
            if (cnt < y[i - 1]){last = i - 1;cnt = y[i - 1];i--;continue;}
        }

        int r = gtspec(i);
        int p = Mxgt(1, 0, n - 1, r, i);
        i = r;
        if (cnt < y[p]){last = p;cnt = y[p];}
    }
    int d = gt(1, 0, n - 1, 0, last);
    return ((d % mod) * (y[last] % mod)) % mod;
}
int init(int N, int X[], int Y[]) {
    n = N;
    for (int i = 0; i < n; i++) {
        x[i] = X[i];
        y[i] = Y[i];
    }
    build(1, 0, n - 1);
    int l = -1;
    for (int i = 0; i < n; i++) {
        if (x[i] == 1) {
            if (l == -1)l = i;
            if (i == n - 1 || x[i + 1] != 1) {
                Lf.insert(l);
                Rf[l] = i;
            }
        } else {
            l = -1;
        }
    }
    Lf.insert(-1); Lf.insert(1010101010);
    return opp();
}

int updateX(int pos, int val) {
    if (x[pos] == 1 && val != 1) {
        auto it = Lf.upper_bound(pos); --it;
        int sv = Rf[*it];
        Lf.erase(it);

        if (*it <= pos - 1) {
            Lf.insert(*it);
            Rf[*it] = pos - 1;
        }
        if (pos + 1 <= sv) {
            Lf.insert(pos + 1);
            Rf[pos + 1] = sv;
        }
    } else if (x[pos] != 1 && val == 1) {
        auto s = Lf.upper_bound(pos);
        auto f = s; --f;
        int S = *s, F = *f;
        if (F != -1 && Rf[F] == pos - 1 && pos + 1 == S) {
            Lf.erase(f);
            Lf.erase(s);

            Lf.insert(F);
            Rf[F] = Rf[S];
        } else if (F != -1 && Rf[F] == pos - 1) {
            Rf[F]++;
        } else if (pos + 1 == S) {
            Lf.erase(s);

            Lf.insert(S - 1);
            Rf[S - 1] = Rf[S];
        }
    }
    x[pos] = val;
    upd(1, 0, n - 1, pos, val);
    return opp();
}

int updateY(int pos, int val) {
    y[pos] = val;
    Mxupd(1, 0, n - 1, pos);
    return opp();
}

/**
0  1  2  3  4  5 6 7 8 9
10 10 10 10 10 1 1 1 1 1
*/

Compilation message (stderr)

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:25:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   25 |     t[v] = ((ll)t[2 * v] * (ll)t[2 * v + 1]) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void upd(int, int, int, int, int)':
horses.cpp:40:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   40 |     t[v] = ((ll)t[2 * v] * (ll)t[2 * v + 1]) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int gt(int, int, int, int, int)':
horses.cpp:59:80: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   59 |     return ((ll)gt(2 * v, vl, vm, l, r) * (ll)gt(2 * v + 1, vm + 1, vr, l, r)) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int opp()':
horses.cpp:102:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |     return ((d % mod) * (y[last] % mod)) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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