oj.uz

Submission #988865

# Submission time Handle Problem Language Result Execution time Memory
988865 2024-05-26T13:46:48 Z bigo Horses (IOI15_horses) C++14
17 / 100
 763 ms 122720 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);
            if (wx.size() > 31)
                wx.pop_back();
        }
    }
    wx.push_back(n);
    reverse(all(wx));
    if (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;
    }
    x[pos] = val;
    segx->upd(pos, val);
    if (wx.size() > 31)
        wx.erase(wx.begin());
    if (wx.size() < 31)
        wx.push_back(-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: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:161:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  161 |     return ans.second;
      |            ~~~~^~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:194:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  194 |     return ans.second;
      |            ~~~~^~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:201:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  201 |     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 1 ms 344 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 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 392 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 0 ms 348 KB Output is correct
2 Correct 0 ms 436 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 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 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 Incorrect 3 ms 604 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 763 ms 122720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.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 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 432 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 440 KB Output is correct
14 Correct 1 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 Incorrect 4 ms 604 KB Output isn't correct
24 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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 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 436 KB Output is correct
8 Correct 0 ms 668 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 1 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 Incorrect 4 ms 604 KB Output isn't correct
24 Halted 0 ms 0 KB -