oj.uz

Submission #988869

# Submission time Handle Problem Language Result Execution time Memory
988869 2024-05-26T13:55:04 Z bigo Horses (IOI15_horses) C++14
77 / 100
 1500 ms 133364 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <utility>
using namespace std;
#define all(a) a.begin(), a.end()
#define rep(i,s,e) for(ll i=s;i<e;i++)
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 1e18;
typedef complex<double> cd;
const double pi = acos(-1);
const ll mod = 1e9 + 7;
const ll mod1 = 1e9 + 9;
const ll mod2 = 998244353;
const ll mac = 31;
const ll MAXN = 4e5 + 2;
typedef vector<int> vi;
typedef vector<vi> vvi;



ll cef(ll a, ll b) {
    ll val;
    if (ll(a) * ll(b) >= 1e9)
        val = 0;
    else
        val = a * b;
    return val;
}

struct seg {
    ll l, r, mid, val = 1, vm = 1;
    seg* lp, * rp;
    seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) {
        if (l < r) {
            lp = new seg(l, mid);
            rp = new seg(mid + 1, r);
        }
    }
    void pull() {
        val = cef(lp->val, rp->val);
        vm = (lp->vm * rp->vm) % mod;
    }
    void upd(ll i, ll x) {
        if (l == r) {
            val = x;
            vm = x % mod;
            return;
        }
        if (i <= mid) lp->upd(i, x);
        else rp->upd(i, x);
        pull();
    }
    ll que(ll a, ll b) {
        if (a <= l and r <= b) return val;
        if (a > r or l > b) return 1;
        return cef(lp->que(a, b), rp->que(a, b));
    }
    ll qm(ll a, ll b) {
        if (a <= l and r <= b)
            return vm;
        if (a > r or l > b)
            return 1;
        return (lp->qm(a, b) * rp->qm(a, b)) % mod;
    }
};

seg* segx;

struct smax {
    int val = 0;
    int mik = 0;
    int l, r, mid;
    smax* lp, * rp;
    smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
        if (l < r) {
            lp = new smax(l, mid);
            rp = new smax(mid + 1, r);
        }
        else if (l == r) {
            mik = l;
        }
    }
    void pull() {
        val = max(lp->val, rp->val);
        mik = lp->mik;
        if (lp->val < rp->val)
            mik = rp->mik;
    }
    void upd(int i, int x) {
        if (l == r) {
            val = x;
            return;
        }
        if (i <= mid) lp->upd(i, x);
        else rp->upd(i, x);
        pull();
    }
    pair<int,int> que(int a, int b) {
        if (a > r || b < l) return { 0,-1 };
        if (a <= l && r <= b) return { val,mik };
        pii op1 = lp->que(a, b), op2 = rp->que(a, b);
        if (op1.first > op2.first)
            return op1;
        else
            return op2;
    }
};

smax* segy;

int n;
vi x, y;
vector<int> wx;

pair<ll, ll> solve() {
    pair<ll, ll>ans = { 0,(x[0] * y[0]) % mod };
    int pr = -1;
    for (int j = wx.size() - 1;j>=0;j--) {
        int i = wx[j];
        if (pr != -1 and pr <= (i - 1)) {
            pair<ll,ll> y1 = segy->que(pr, i - 1);
            ll t = cef(y1.first, segx->que(ans.first + 1, i - 1));
            if (t == 0 or t >= y[ans.first])
                ans = { y1.second,(segx->qm(0,i - 1) * y1.first) % mod };
        }
        if (i != -1 and i != n) {
            ll t = cef(segx->que(ans.first + 1, i), y[i]);
            if (t == 0 or t >= y[ans.first])
                ans = { i,(segx->qm(0,i) * y[i]) % mod };
        }

        pr = i + 1;
    }
    return ans;
}
int init(int N, int X[], int Y[]) {
    n = N;
    x.resize(n);
    y.resize(n);
    segx = new seg(0, n - 1);
    segy = new smax(0, n - 1);
    wx.push_back(-1);
    rep(i, 0, n) {
        x[i] = X[i], y[i] = Y[i];
        segx->upd(i, x[i]);
        segy->upd(i, y[i]);
        if (x[i] > 1)
            wx.push_back(i);
    }
    wx.push_back(n);
    reverse(all(wx));
    while(wx.size() > 31)
        wx.pop_back();

    pair<ll, ll> ans = solve();
    return ans.second;
}

int updateX(int pos, int val) {
    vector<int>tmp;
    if (x[pos] > 1 and val==1) {
        for (int i : wx) if (i != pos) {
            tmp.push_back(i);
        }
        wx = tmp;
    }
    else if (x[pos] == 1 and val > 1) {
        bool flag = false;
        for (int i : wx) {
            if (i > pos)
                tmp.push_back(i);
            else if (!flag) {
                tmp.push_back(pos);
                tmp.push_back(i);
                flag = true;
            }
            else
                tmp.push_back(i);
        }
        wx = tmp;
    }
    if (wx.size() > 31)
        wx.pop_back();
    if (wx.size() < 31)
        wx.push_back(-1);
    x[pos] = val;
    segx->upd(pos, val);
    pair<ll, ll> ans = solve();
    return ans.second;
}

int updateY(int pos, int val) {
    y[pos] = val;
    segy->upd(pos, val);
    pair<ll, ll> ans = solve();
    return ans.second;
}

Compilation message

horses.cpp: In function 'll cef(ll, ll)':
horses.cpp:25:15: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
   25 |     if (ll(a) * ll(b) >= 1e9)
      |         ~~~~~~^~~~~~~
horses.cpp: In constructor 'seg::seg(ll, ll)':
horses.cpp:35:18: warning: declaration of 'r' shadows a member of 'seg' [-Wshadow]
   35 |     seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) {
      |               ~~~^
horses.cpp:33:11: note: shadowed declaration is here
   33 |     ll l, r, mid, val = 1, vm = 1;
      |           ^
horses.cpp:35:12: warning: declaration of 'l' shadows a member of 'seg' [-Wshadow]
   35 |     seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) {
      |         ~~~^
horses.cpp:33:8: note: shadowed declaration is here
   33 |     ll l, r, mid, val = 1, vm = 1;
      |        ^
horses.cpp: In constructor 'seg::seg(ll, ll)':
horses.cpp:35:18: warning: declaration of 'r' shadows a member of 'seg' [-Wshadow]
   35 |     seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) {
      |               ~~~^
horses.cpp:33:11: note: shadowed declaration is here
   33 |     ll l, r, mid, val = 1, vm = 1;
      |           ^
horses.cpp:35:12: warning: declaration of 'l' shadows a member of 'seg' [-Wshadow]
   35 |     seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) {
      |         ~~~^
horses.cpp:33:8: note: shadowed declaration is here
   33 |     ll l, r, mid, val = 1, vm = 1;
      |        ^
horses.cpp: In constructor 'seg::seg(ll, ll)':
horses.cpp:35:18: warning: declaration of 'r' shadows a member of 'seg' [-Wshadow]
   35 |     seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) {
      |               ~~~^
horses.cpp:33:11: note: shadowed declaration is here
   33 |     ll l, r, mid, val = 1, vm = 1;
      |           ^
horses.cpp:35:12: warning: declaration of 'l' shadows a member of 'seg' [-Wshadow]
   35 |     seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) {
      |         ~~~^
horses.cpp:33:8: note: shadowed declaration is here
   33 |     ll l, r, mid, val = 1, vm = 1;
      |        ^
horses.cpp: In constructor 'smax::smax(int, int)':
horses.cpp:76:21: warning: declaration of 'r' shadows a member of 'smax' [-Wshadow]
   76 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |                 ~~~~^
horses.cpp:74:12: note: shadowed declaration is here
   74 |     int l, r, mid;
      |            ^
horses.cpp:76:14: warning: declaration of 'l' shadows a member of 'smax' [-Wshadow]
   76 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |          ~~~~^
horses.cpp:74:9: note: shadowed declaration is here
   74 |     int l, r, mid;
      |         ^
horses.cpp: In constructor 'smax::smax(int, int)':
horses.cpp:76:21: warning: declaration of 'r' shadows a member of 'smax' [-Wshadow]
   76 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |                 ~~~~^
horses.cpp:74:12: note: shadowed declaration is here
   74 |     int l, r, mid;
      |            ^
horses.cpp:76:14: warning: declaration of 'l' shadows a member of 'smax' [-Wshadow]
   76 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |          ~~~~^
horses.cpp:74:9: note: shadowed declaration is here
   74 |     int l, r, mid;
      |         ^
horses.cpp: In constructor 'smax::smax(int, int)':
horses.cpp:76:21: warning: declaration of 'r' shadows a member of 'smax' [-Wshadow]
   76 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |                 ~~~~^
horses.cpp:74:12: note: shadowed declaration is here
   74 |     int l, r, mid;
      |            ^
horses.cpp:76:14: warning: declaration of 'l' shadows a member of 'smax' [-Wshadow]
   76 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |          ~~~~^
horses.cpp:74:9: note: shadowed declaration is here
   74 |     int l, r, mid;
      |         ^
horses.cpp: In function 'std::pair<long long int, long long int> solve()':
horses.cpp:120:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  120 |     for (int j = wx.size() - 1;j>=0;j--) {
      |                  ~~~~~~~~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:148:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  148 |         segy->upd(i, y[i]);
      |                   ^
horses.cpp:150:26: warning: conversion from 'll' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
  150 |             wx.push_back(i);
      |                          ^
horses.cpp:158:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  158 |     return ans.second;
      |            ~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:191:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  191 |     return ans.second;
      |            ~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:198:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  198 |     return ans.second;
      |            ~~~~^~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 436 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 420 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 8 ms 696 KB Output is correct
24 Correct 6 ms 604 KB Output is correct
25 Correct 3 ms 604 KB Output is correct
26 Correct 4 ms 604 KB Output is correct
27 Correct 6 ms 604 KB Output is correct
28 Correct 8 ms 708 KB Output is correct
29 Correct 2 ms 600 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 6 ms 692 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 122912 KB Output is correct
2 Correct 921 ms 127436 KB Output is correct
3 Correct 948 ms 123060 KB Output is correct
4 Correct 851 ms 124868 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 436 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 432 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 436 KB Output is correct
23 Correct 7 ms 692 KB Output is correct
24 Correct 4 ms 604 KB Output is correct
25 Correct 3 ms 604 KB Output is correct
26 Correct 3 ms 600 KB Output is correct
27 Correct 6 ms 604 KB Output is correct
28 Correct 5 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 2 ms 692 KB Output is correct
32 Correct 6 ms 604 KB Output is correct
33 Correct 416 ms 121700 KB Output is correct
34 Correct 278 ms 121684 KB Output is correct
35 Correct 295 ms 130708 KB Output is correct
36 Correct 296 ms 130756 KB Output is correct
37 Correct 396 ms 120148 KB Output is correct
38 Correct 301 ms 122056 KB Output is correct
39 Correct 221 ms 119892 KB Output is correct
40 Correct 247 ms 125944 KB Output is correct
41 Correct 234 ms 119888 KB Output is correct
42 Correct 312 ms 119936 KB Output is correct
43 Correct 222 ms 126152 KB Output is correct
44 Correct 257 ms 126160 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 600 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 7 ms 604 KB Output is correct
24 Correct 5 ms 604 KB Output is correct
25 Correct 3 ms 604 KB Output is correct
26 Correct 4 ms 472 KB Output is correct
27 Correct 7 ms 604 KB Output is correct
28 Correct 7 ms 448 KB Output is correct
29 Correct 3 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 6 ms 604 KB Output is correct
33 Correct 559 ms 124668 KB Output is correct
34 Correct 921 ms 133364 KB Output is correct
35 Correct 869 ms 124672 KB Output is correct
36 Correct 873 ms 128388 KB Output is correct
37 Correct 392 ms 121868 KB Output is correct
38 Correct 277 ms 121704 KB Output is correct
39 Correct 290 ms 130764 KB Output is correct
40 Correct 333 ms 130760 KB Output is correct
41 Correct 379 ms 119888 KB Output is correct
42 Correct 314 ms 122048 KB Output is correct
43 Correct 217 ms 119916 KB Output is correct
44 Correct 245 ms 125900 KB Output is correct
45 Correct 239 ms 119888 KB Output is correct
46 Correct 311 ms 119996 KB Output is correct
47 Correct 215 ms 126204 KB Output is correct
48 Correct 225 ms 126180 KB Output is correct
49 Execution timed out 1571 ms 123476 KB Time limit exceeded
50 Halted 0 ms 0 KB -