oj.uz

Submission #988835

# Submission time Handle Problem Language Result Execution time Memory
988835 2024-05-26T12:31:56 Z bigo Horses (IOI15_horses) C++14
37 / 100
 972 ms 131408 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 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);
        }
    }
    void pull() {
        val = max(lp->val, rp->val);
    }
    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();
    }
    int que(int a, int b) {
        if (a > r || b < l) return 0;
        if (a <= l && r <= b) return val;
        return max(lp->que(a, b), rp->que(a, b));
    }
};

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)) {
            ll y1 = segy->que(pr, i - 1);
            ll t = cef(y1, segx->que(ans.first + 1, i - 1));
            if (t == 0 or t >= y[ans.first])
                ans = { i-1,(segx->qm(0,i - 1) * y1) % 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;
}

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:75:21: warning: declaration of 'r' shadows a member of 'smax' [-Wshadow]
   75 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |                 ~~~~^
horses.cpp:73:12: note: shadowed declaration is here
   73 |     int l, r, mid;
      |            ^
horses.cpp:75:14: warning: declaration of 'l' shadows a member of 'smax' [-Wshadow]
   75 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |          ~~~~^
horses.cpp:73:9: note: shadowed declaration is here
   73 |     int l, r, mid;
      |         ^
horses.cpp: In constructor 'smax::smax(int, int)':
horses.cpp:75:21: warning: declaration of 'r' shadows a member of 'smax' [-Wshadow]
   75 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |                 ~~~~^
horses.cpp:73:12: note: shadowed declaration is here
   73 |     int l, r, mid;
      |            ^
horses.cpp:75:14: warning: declaration of 'l' shadows a member of 'smax' [-Wshadow]
   75 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |          ~~~~^
horses.cpp:73:9: note: shadowed declaration is here
   73 |     int l, r, mid;
      |         ^
horses.cpp: In constructor 'smax::smax(int, int)':
horses.cpp:75:21: warning: declaration of 'r' shadows a member of 'smax' [-Wshadow]
   75 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |                 ~~~~^
horses.cpp:73:12: note: shadowed declaration is here
   73 |     int l, r, mid;
      |            ^
horses.cpp:75:14: warning: declaration of 'l' shadows a member of 'smax' [-Wshadow]
   75 |     smax(int l, int r) : l(l), r(r), mid((l + r) / 2) {
      |          ~~~~^
horses.cpp:73:9: note: shadowed declaration is here
   73 |     int l, r, mid;
      |         ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:137:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  137 |         segy->upd(i, y[i]);
      |                   ^
horses.cpp:139:23: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
  139 |             wx.insert(i);
      |                       ^
horses.cpp:145:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  145 |     return ans.second;
      |            ~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:161:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  161 |     return ans.second;
      |            ~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:168:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  168 |     return ans.second;
      |            ~~~~^~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 604 KB Output is correct
9 Correct 1 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 1 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 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 352 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 344 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 376 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 436 KB Output is correct
17 Correct 0 ms 604 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 Incorrect 0 ms 348 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 122448 KB Output is correct
2 Correct 972 ms 131408 KB Output is correct
3 Correct 916 ms 122384 KB Output is correct
4 Correct 881 ms 126364 KB Output is correct

Subtask #4
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 436 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 1 ms 344 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 Incorrect 0 ms 348 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 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 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 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 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 Halted 0 ms 0 KB -