Submission #988849

#	Time	Username	Problem	Language	Result	Execution time	Memory
988849		bigo	Horses (IOI15_horses)	C++14	77 / 100	1568 ms	131172 KiB

horses

#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 (stderr)

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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 0 / 23