Submission #438182

#	Time	Username	Problem	Language	Result	Execution time	Memory
438182		illyakr	Horses (IOI15_horses)	C++14	77 / 100	1591 ms	55640 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;
#define ll long long
const ll mod = 1000000007;
const ll mx = 1000000018;

ll n;
ll x[501010], y[501010];
ll t[2010101];
ll Mxt[2010101];

int Ri[2010101];
int Le[2010101];
int prRi[2010101];
int goLe[2010101];
void push(int v, int vl, int vr) {
    if (goLe[v] != -2) {
        if (vl == vr) {
            Le[v] = goLe[v];
        } else {
            goLe[2 * v] = goLe[v];
            goLe[2 * v + 1] = goLe[v];
        }
    }
    if (prRi[v] != -2) {
        if (vl == vr) {
            Ri[v] = prRi[v];
        } else {
            prRi[2 * v] = prRi[v];
            prRi[2 * v + 1] = prRi[v];
        }
    }
    goLe[v] = -2;
    prRi[v] = -2;
}
void updspec(int v, int vl, int vr, int l, int r, int val, int ty) {
    push(v, vl, vr);
    if (l <= vl && vr <= r) {
        if (ty == 1)goLe[v] = val;
        if (ty == 2)prRi[v] = val;
        push(v, vl, vr);
        return;
    }
    if (r < vl || vr < l)return;
    int vm = (vl + vr) / 2;
    updspec(2 * v, vl, vm, l, r, val, ty);
    updspec(2 * v + 1, vm + 1, vr, l, r, val, ty);
}
pair<int, int> gtspec(int v, int vl, int vr, int pos) {
    push(v, vl, vr);
    if (vl == vr)return {Le[v], Ri[v]};
    int vm = (vl + vr) / 2;
    if (pos <= vm)return gtspec(2 * v, vl, vm, pos);
    else return gtspec(2 * v + 1, vm + 1, vr, pos);
}

void build(int v, int vl, int vr) {
    goLe[v] = -2;
    prRi[v] = -2;
    if (vl == vr) {
        t[v] = x[vl] % mod;
        Mxt[v] = vl;
        return;
    }
    int vm = (vl + vr) / 2;
    build(2 * v, vl, vm);
    build(2 * v + 1, vm + 1, vr);
    t[v] = (t[2 * v] * 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, ll 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] = (t[2 * v] * 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];
}
ll 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 (gt(2 * v, vl, vm, l, r) * gt(2 * v + 1, vm + 1, vr, l, r)) % mod;
}
ll 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;
    ll f = Mxgt(2 * v, vl, vm, l, r);
    ll 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;
}

int opp() {
    ll cnt = y[n - 1];
    ll 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;}
        }

        auto [r, S] = gtspec(1, 0, n - 1, i);
        int p = Mxgt(1, 0, n - 1, r, i);
        i = r;
        if (cnt < y[p]){last = p;cnt = y[p];}
    }
    ll 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 (ll i = 0; i < n; i++) {
        x[i] = X[i];
        y[i] = Y[i];
	}
	build(1, 0, n - 1);
    int lft = -1;
    for (int i = 0; i < n; i++) {
        updspec(1, 0, n - 1, i, i, lft, 1);
        if (x[i] > 1)lft = i;
    }
    int rgt = n;
    for (int i = n - 1; i >= 0; i--) {
        updspec(1, 0, n - 1, i, i, rgt, 2);
        if (x[i] > 1)rgt = i;
    }
//    for (int i = 0; i < n; i++) {
//        auto qq = gtspec(1, 0, n - 1, i);
//        s << i << " --   " << qq.first << " " << qq.second << endl;
//    }
    return opp();
}

int updateX(int pos, int val) {
    x[pos] = val;
    upd(1, 0, n - 1, pos, val);
    if (val == 0)exit(1);
    if (val == 1) {
        auto [Lf, Rt] = gtspec(1, 0, n - 1, pos);
        updspec(1, 0, n - 1, Lf + 1, Rt, Lf, 1);
        updspec(1, 0, n - 1, Lf, Rt - 1, Rt, 2);
    } else {
        auto [Lf, Rt] = gtspec(1, 0, n - 1, pos);
        updspec(1, 0, n - 1, pos + 1, Rt, pos, 1);
        updspec(1, 0, n - 1, Lf, pos - 1, pos, 2);
    }
	return opp();
}

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

Compilation message (stderr)

horses.cpp: In function 'int opp()':
horses.cpp:120:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |     for (int i = n - 1; i > 0;) {
      |                  ~~^~~
horses.cpp:128:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |         auto [r, S] = gtspec(1, 0, n - 1, i);
      |              ^
horses.cpp:128:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |         auto [r, S] = gtspec(1, 0, n - 1, i);
      |                                    ~~^~~
horses.cpp:129:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  129 |         int p = Mxgt(1, 0, n - 1, r, i);
      |                            ~~^~~
horses.cpp:129:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  129 |         int p = Mxgt(1, 0, n - 1, r, i);
      |                 ~~~~^~~~~~~~~~~~~~~~~~~
horses.cpp:133:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  133 |     ll d = gt(1, 0, n - 1, 0, last);
      |                     ~~^~~
horses.cpp:133:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  133 |     ll d = gt(1, 0, n - 1, 0, last);
      |                               ^~~~
horses.cpp:134:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  134 |     return ((d % mod) * (y[last] % mod)) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:142:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  142 |  build(1, 0, n - 1);
      |              ~~^~~
horses.cpp:145:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  145 |         updspec(1, 0, n - 1, i, i, lft, 1);
      |                       ~~^~~
horses.cpp:148:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  148 |     int rgt = n;
      |               ^
horses.cpp:149:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  149 |     for (int i = n - 1; i >= 0; i--) {
      |                  ~~^~~
horses.cpp:150:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  150 |         updspec(1, 0, n - 1, i, i, rgt, 2);
      |                       ~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:162:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  162 |     upd(1, 0, n - 1, pos, val);
      |               ~~^~~
horses.cpp:165:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  165 |         auto [Lf, Rt] = gtspec(1, 0, n - 1, pos);
      |              ^
horses.cpp:165:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  165 |         auto [Lf, Rt] = gtspec(1, 0, n - 1, pos);
      |                                      ~~^~~
horses.cpp:166:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  166 |         updspec(1, 0, n - 1, Lf + 1, Rt, Lf, 1);
      |                       ~~^~~
horses.cpp:167:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  167 |         updspec(1, 0, n - 1, Lf, Rt - 1, Rt, 2);
      |                       ~~^~~
horses.cpp:169:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  169 |         auto [Lf, Rt] = gtspec(1, 0, n - 1, pos);
      |              ^
horses.cpp:169:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  169 |         auto [Lf, Rt] = gtspec(1, 0, n - 1, pos);
      |                                      ~~^~~
horses.cpp:170:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  170 |         updspec(1, 0, n - 1, pos + 1, Rt, pos, 1);
      |                       ~~^~~
horses.cpp:171:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  171 |         updspec(1, 0, n - 1, Lf, pos - 1, pos, 2);
      |                       ~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:178:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  178 |     Mxupd(1, 0, n - 1, pos);
      |                 ~~^~~

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