oj.uz

Submission #988849

# Submission time Handle Problem Language Result Execution time Memory
988849 2024-05-26T13:02:51 Z bigo Horses (IOI15_horses) C++14
77 / 100
 1500 ms 131172 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;
set<int> wx;

pair<ll, ll> solve() {
    pair<ll, ll>ans = { 0,(x[0] * y[0]) % mod };
    int pr = -1;
    for (int i : wx) {
        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.insert(-1);
    wx.insert(n);
    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.insert(i);
            if (wx.size() > 31)
                wx.erase(wx.begin());
        }
    }
    pair<ll, ll> ans = solve();
    return ans.second;
}

int updateX(int pos, int val) {
    if (x[pos] > 1)
        wx.erase(pos);
    x[pos] = val;
    segx->upd(pos, val);
    if (x[pos] > 1) {
        wx.insert(pos);
        if (wx.size() > 31)
            wx.erase(wx.begin());
    }
    if (wx.size() < 31)
        wx.insert(-1);
    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;
}
/*
int main() {
    int n, q;
    cin >> n;
    int x[10], y[10];
    rep(i, 0, n)
        cin >> x[i];
    rep(i, 0, n)
        cin >> y[i];
    cout << init(n, x, y) << "\n";
    cin >> q;
    while (q--) {
        ll t, pos, val;
        cin >> t >> pos >> val;
        if (t == 1)
            cout << updateX(pos, val) << "\n";
        else
            cout << updateY(pos, val) << "\n";
    }
}*/

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 '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:23: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
  150 |             wx.insert(i);
      |                       ^
horses.cpp:156:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  156 |     return ans.second;
      |            ~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:172:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  172 |     return ans.second;
      |            ~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:179:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  179 |     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 1 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 1 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 1 ms 348 KB Output is correct
10 Correct 1 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 344 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 1 ms 348 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 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 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 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 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 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 4 ms 600 KB Output is correct
25 Correct 3 ms 712 KB Output is correct
26 Correct 3 ms 604 KB Output is correct
27 Correct 10 ms 600 KB Output is correct
28 Correct 5 ms 604 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 1 ms 692 KB Output is correct
31 Correct 3 ms 604 KB Output is correct
32 Correct 6 ms 604 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 121940 KB Output is correct
2 Correct 980 ms 128812 KB Output is correct
3 Correct 896 ms 121920 KB Output is correct
4 Correct 863 ms 124756 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 1 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 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 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 7 ms 604 KB Output is correct
24 Correct 4 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 7 ms 604 KB Output is correct
28 Correct 5 ms 696 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 1 ms 708 KB Output is correct
31 Correct 3 ms 604 KB Output is correct
32 Correct 6 ms 604 KB Output is correct
33 Correct 411 ms 121680 KB Output is correct
34 Correct 288 ms 121684 KB Output is correct
35 Correct 302 ms 128592 KB Output is correct
36 Correct 308 ms 128592 KB Output is correct
37 Correct 375 ms 119892 KB Output is correct
38 Correct 318 ms 120792 KB Output is correct
39 Correct 219 ms 119888 KB Output is correct
40 Correct 246 ms 123624 KB Output is correct
41 Correct 233 ms 119888 KB Output is correct
42 Correct 321 ms 120244 KB Output is correct
43 Correct 244 ms 123988 KB Output is correct
44 Correct 249 ms 123988 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 440 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 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 436 KB Output is correct
15 Correct 1 ms 344 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 344 KB Output is correct
19 Correct 0 ms 344 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 7 ms 604 KB Output is correct
24 Correct 4 ms 604 KB Output is correct
25 Correct 3 ms 708 KB Output is correct
26 Correct 3 ms 604 KB Output is correct
27 Correct 9 ms 604 KB Output is correct
28 Correct 6 ms 604 KB Output is correct
29 Correct 2 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 600 KB Output is correct
33 Correct 585 ms 122572 KB Output is correct
34 Correct 954 ms 131172 KB Output is correct
35 Correct 871 ms 122448 KB Output is correct
36 Correct 935 ms 126360 KB Output is correct
37 Correct 436 ms 122080 KB Output is correct
38 Correct 285 ms 121664 KB Output is correct
39 Correct 309 ms 128564 KB Output is correct
40 Correct 322 ms 128692 KB Output is correct
41 Correct 373 ms 119948 KB Output is correct
42 Correct 321 ms 120912 KB Output is correct
43 Correct 217 ms 119892 KB Output is correct
44 Correct 246 ms 123732 KB Output is correct
45 Correct 238 ms 119888 KB Output is correct
46 Correct 306 ms 119892 KB Output is correct
47 Correct 249 ms 124204 KB Output is correct
48 Correct 265 ms 124156 KB Output is correct
49 Execution timed out 1568 ms 123476 KB Time limit exceeded
50 Halted 0 ms 0 KB -