oj.uz

Submission #438182

# Submission time Handle Problem Language Result Execution time Memory
438182 2021-06-27T18:09:21 Z illyakr Horses (IOI15_horses) C++14
77 / 100
 1500 ms 55640 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 268 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 3 ms 464 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 8 ms 456 KB Output is correct
28 Correct 4 ms 460 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 7 ms 460 KB Output is correct
32 Correct 10 ms 460 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1287 ms 47732 KB Output is correct
2 Correct 529 ms 48984 KB Output is correct
3 Correct 621 ms 46524 KB Output is correct
4 Correct 560 ms 46408 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 3 ms 380 KB Output is correct
24 Correct 2 ms 436 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 8 ms 460 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 3 ms 332 KB Output is correct
30 Correct 2 ms 464 KB Output is correct
31 Correct 5 ms 432 KB Output is correct
32 Correct 7 ms 460 KB Output is correct
33 Correct 370 ms 45504 KB Output is correct
34 Correct 354 ms 45484 KB Output is correct
35 Correct 437 ms 45032 KB Output is correct
36 Correct 371 ms 44964 KB Output is correct
37 Correct 490 ms 45180 KB Output is correct
38 Correct 370 ms 45912 KB Output is correct
39 Correct 402 ms 44956 KB Output is correct
40 Correct 365 ms 48964 KB Output is correct
41 Correct 411 ms 44948 KB Output is correct
42 Correct 448 ms 45136 KB Output is correct
43 Correct 358 ms 49340 KB Output is correct
44 Correct 355 ms 49300 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 7 ms 460 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 440 KB Output is correct
31 Correct 5 ms 460 KB Output is correct
32 Correct 8 ms 460 KB Output is correct
33 Correct 1278 ms 47628 KB Output is correct
34 Correct 526 ms 45820 KB Output is correct
35 Correct 621 ms 46516 KB Output is correct
36 Correct 603 ms 46424 KB Output is correct
37 Correct 371 ms 45532 KB Output is correct
38 Correct 360 ms 45520 KB Output is correct
39 Correct 397 ms 45068 KB Output is correct
40 Correct 372 ms 44996 KB Output is correct
41 Correct 489 ms 45056 KB Output is correct
42 Correct 374 ms 45888 KB Output is correct
43 Correct 357 ms 44864 KB Output is correct
44 Correct 373 ms 48844 KB Output is correct
45 Correct 417 ms 44924 KB Output is correct
46 Correct 457 ms 45076 KB Output is correct
47 Correct 362 ms 49292 KB Output is correct
48 Correct 376 ms 49320 KB Output is correct
49 Correct 627 ms 48780 KB Output is correct
50 Correct 535 ms 48816 KB Output is correct
51 Correct 744 ms 55640 KB Output is correct
52 Correct 445 ms 55100 KB Output is correct
53 Execution timed out 1591 ms 47172 KB Time limit exceeded
54 Halted 0 ms 0 KB -