oj.uz

Submission #760387

# Submission time Handle Problem Language Result Execution time Memory
760387 2023-06-17T14:24:30 Z GrindMachine Horses (IOI15_horses) C++17
100 / 100
 377 ms 52320 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

sell at exactly 1 place

*/

const int MOD = 1e9 + 7;
const int N = 5e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "horses.h"

template<typename T>
struct segtree1 {
    // https://codeforces.com/blog/entry/18051
 
    /*=======================================================*/
 
    struct data {
    	ll a;
    };
 
    data neutral = {1};
 
    data merge(data &left, data &right) {
    	data curr;
    	curr.a = left.a * right.a % MOD;
    	return curr;
    }
 
    void create(int i, T v) {
    	tr[i].a = v;
    }
 
    void modify(int i, T v) {
    	tr[i].a = v;
    }
 
    /*=======================================================*/
 
    int n;
    vector<data> tr;
 
    segtree1() {
 
    }
 
    segtree1(int siz) {
        init(siz);
    }
 
    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }
 
    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }
 
    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }
 
    data query(int l, int r) {
        data resl = neutral, resr = neutral;
 
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }
 
        return merge(resl, resr);
    }
};

template<typename T>
struct segtree2 {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
    	ll a;
    };

    data neutral = {0};

    data merge(data &left, data &right) {
    	data curr;
    	curr.a = max(left.a,right.a);
    	return curr;
    }

    void create(int i, T v) {
    	tr[i].a = v;
    }

    void modify(int i, T v) {
    	tr[i].a = v;
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree2() {

    }

    segtree2(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

ll n;
vector<ll> a(N), b(N);
set<ll> active;
segtree1<ll> st_prod(N);
segtree2<ll> st_max(N);

int get_ans(){
	ll prod = 1;
	vector<ll> points;
	points.pb(n);

	bool big = false;

	for(auto it = active.rbegin(); it != active.rend(); ++it){
		ll pos = *it;
		prod *= a[pos];
		points.pb(pos);

		if(prod > inf1){
			big = true;
			break;
		}
	}

	if(!big and points.back() != 0){
		points.pb(0);
	}

	reverse(all(points));

	ll befprod = st_prod.query(0,points.front()-1).a;
	__int128 curr = 1;
	__int128 best = 0;

	rep(i,sz(points)-1){
		curr *= a[points[i]];
		ll l = points[i], r = points[i+1]-1;
		ll mxb = st_max.query(l,r).a;
		amax(best, curr * mxb);
	}

	ll ans = (best % MOD) * befprod % MOD;
	return ans;
}

int init(int n_, int X[], int Y[]) {
	n = n_;
	rep(i,n) a[i] = X[i], b[i] = Y[i];

	rep(i,n){
		if(a[i] > 1){
			active.insert(i);
		}

		st_prod.pupd(i,a[i]);
		st_max.pupd(i,b[i]);
	}

	return get_ans();
}

int updateX(int pos, int val) {
	if(a[pos] > 1){
		active.erase(pos);
	}

	a[pos] = val;
	st_prod.pupd(pos,val);

	if(a[pos] > 1){
		active.insert(pos);
	}

	return get_ans();	
}

int updateY(int pos, int val) {
	b[pos] = val;
	st_max.pupd(pos,val);
	return get_ans();
}

Compilation message

horses.cpp: In function 'int get_ans()':
horses.cpp:226:45: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  226 |  ll befprod = st_prod.query(0,points.front()-1).a;
      |                               ~~~~~~~~~~~~~~^~
horses.cpp:30:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | #define rep(i, n) for(int i = 0; i < n; ++i)
......
  230 |  rep(i,sz(points)-1){
      |      ~~~~~~~~~~~~~~                 
horses.cpp:230:2: note: in expansion of macro 'rep'
  230 |  rep(i,sz(points)-1){
      |  ^~~
horses.cpp:233:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  233 |   ll mxb = st_max.query(l,r).a;
      |                         ^
horses.cpp:233:27: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  233 |   ll mxb = st_max.query(l,r).a;
      |                           ^
horses.cpp:237:34: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
  237 |  ll ans = (best % MOD) * befprod % MOD;
      |           ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:238:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  238 |  return ans;
      |         ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23744 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 9 ms 23720 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 9 ms 23764 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 8 ms 23764 KB Output is correct
9 Correct 9 ms 23764 KB Output is correct
10 Correct 9 ms 23764 KB Output is correct
11 Correct 9 ms 23764 KB Output is correct
12 Correct 11 ms 23764 KB Output is correct
13 Correct 13 ms 23760 KB Output is correct
14 Correct 10 ms 23764 KB Output is correct
15 Correct 9 ms 23764 KB Output is correct
16 Correct 9 ms 23764 KB Output is correct
17 Correct 13 ms 23716 KB Output is correct
18 Correct 11 ms 23724 KB Output is correct
19 Correct 12 ms 23764 KB Output is correct
20 Correct 11 ms 23764 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23732 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 9 ms 23764 KB Output is correct
4 Correct 8 ms 23764 KB Output is correct
5 Correct 12 ms 23804 KB Output is correct
6 Correct 10 ms 23808 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 10 ms 23764 KB Output is correct
10 Correct 10 ms 23760 KB Output is correct
11 Correct 10 ms 23688 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 10 ms 23764 KB Output is correct
15 Correct 10 ms 23764 KB Output is correct
16 Correct 13 ms 23692 KB Output is correct
17 Correct 11 ms 23704 KB Output is correct
18 Correct 10 ms 23764 KB Output is correct
19 Correct 10 ms 23792 KB Output is correct
20 Correct 10 ms 23792 KB Output is correct
21 Correct 10 ms 23764 KB Output is correct
22 Correct 10 ms 23748 KB Output is correct
23 Correct 13 ms 23808 KB Output is correct
24 Correct 10 ms 23724 KB Output is correct
25 Correct 10 ms 23820 KB Output is correct
26 Correct 10 ms 23804 KB Output is correct
27 Correct 11 ms 23704 KB Output is correct
28 Correct 10 ms 23764 KB Output is correct
29 Correct 10 ms 23764 KB Output is correct
30 Correct 10 ms 23764 KB Output is correct
31 Correct 13 ms 23728 KB Output is correct
32 Correct 10 ms 23764 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 52168 KB Output is correct
2 Correct 369 ms 52120 KB Output is correct
3 Correct 304 ms 52096 KB Output is correct
4 Correct 377 ms 52240 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 9 ms 23676 KB Output is correct
4 Correct 9 ms 23784 KB Output is correct
5 Correct 9 ms 23764 KB Output is correct
6 Correct 10 ms 23764 KB Output is correct
7 Correct 10 ms 23752 KB Output is correct
8 Correct 10 ms 23764 KB Output is correct
9 Correct 10 ms 23764 KB Output is correct
10 Correct 9 ms 23764 KB Output is correct
11 Correct 11 ms 23704 KB Output is correct
12 Correct 13 ms 23776 KB Output is correct
13 Correct 11 ms 23704 KB Output is correct
14 Correct 10 ms 23764 KB Output is correct
15 Correct 10 ms 23676 KB Output is correct
16 Correct 10 ms 23800 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 11 ms 23764 KB Output is correct
19 Correct 10 ms 23692 KB Output is correct
20 Correct 12 ms 23732 KB Output is correct
21 Correct 9 ms 23796 KB Output is correct
22 Correct 9 ms 23680 KB Output is correct
23 Correct 12 ms 23784 KB Output is correct
24 Correct 10 ms 23764 KB Output is correct
25 Correct 10 ms 23868 KB Output is correct
26 Correct 10 ms 23860 KB Output is correct
27 Correct 10 ms 23788 KB Output is correct
28 Correct 10 ms 23764 KB Output is correct
29 Correct 12 ms 23784 KB Output is correct
30 Correct 10 ms 23800 KB Output is correct
31 Correct 12 ms 23812 KB Output is correct
32 Correct 10 ms 23804 KB Output is correct
33 Correct 101 ms 27896 KB Output is correct
34 Correct 108 ms 27880 KB Output is correct
35 Correct 219 ms 51300 KB Output is correct
36 Correct 216 ms 51400 KB Output is correct
37 Correct 108 ms 27880 KB Output is correct
38 Correct 149 ms 39808 KB Output is correct
39 Correct 92 ms 27728 KB Output is correct
40 Correct 211 ms 51344 KB Output is correct
41 Correct 102 ms 28012 KB Output is correct
42 Correct 102 ms 27840 KB Output is correct
43 Correct 199 ms 51228 KB Output is correct
44 Correct 201 ms 51200 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Correct 10 ms 23764 KB Output is correct
3 Correct 10 ms 23716 KB Output is correct
4 Correct 10 ms 23764 KB Output is correct
5 Correct 10 ms 23788 KB Output is correct
6 Correct 10 ms 23764 KB Output is correct
7 Correct 12 ms 23752 KB Output is correct
8 Correct 10 ms 23732 KB Output is correct
9 Correct 10 ms 23764 KB Output is correct
10 Correct 10 ms 23764 KB Output is correct
11 Correct 11 ms 23764 KB Output is correct
12 Correct 10 ms 23764 KB Output is correct
13 Correct 10 ms 23764 KB Output is correct
14 Correct 10 ms 23764 KB Output is correct
15 Correct 10 ms 23764 KB Output is correct
16 Correct 11 ms 23716 KB Output is correct
17 Correct 10 ms 23700 KB Output is correct
18 Correct 10 ms 23764 KB Output is correct
19 Correct 11 ms 23764 KB Output is correct
20 Correct 11 ms 23780 KB Output is correct
21 Correct 11 ms 23680 KB Output is correct
22 Correct 10 ms 23764 KB Output is correct
23 Correct 12 ms 23840 KB Output is correct
24 Correct 11 ms 23720 KB Output is correct
25 Correct 14 ms 23764 KB Output is correct
26 Correct 11 ms 23804 KB Output is correct
27 Correct 13 ms 23764 KB Output is correct
28 Correct 12 ms 23832 KB Output is correct
29 Correct 10 ms 23764 KB Output is correct
30 Correct 10 ms 23776 KB Output is correct
31 Correct 11 ms 23764 KB Output is correct
32 Correct 10 ms 23816 KB Output is correct
33 Correct 259 ms 52140 KB Output is correct
34 Correct 312 ms 52252 KB Output is correct
35 Correct 309 ms 52120 KB Output is correct
36 Correct 350 ms 52236 KB Output is correct
37 Correct 104 ms 27852 KB Output is correct
38 Correct 100 ms 27980 KB Output is correct
39 Correct 219 ms 51428 KB Output is correct
40 Correct 218 ms 51312 KB Output is correct
41 Correct 101 ms 27844 KB Output is correct
42 Correct 162 ms 39812 KB Output is correct
43 Correct 93 ms 27732 KB Output is correct
44 Correct 203 ms 51392 KB Output is correct
45 Correct 94 ms 27852 KB Output is correct
46 Correct 96 ms 27832 KB Output is correct
47 Correct 227 ms 51256 KB Output is correct
48 Correct 200 ms 51280 KB Output is correct
49 Correct 155 ms 29884 KB Output is correct
50 Correct 153 ms 29912 KB Output is correct
51 Correct 267 ms 52220 KB Output is correct
52 Correct 250 ms 52300 KB Output is correct
53 Correct 204 ms 29932 KB Output is correct
54 Correct 210 ms 42720 KB Output is correct
55 Correct 135 ms 28040 KB Output is correct
56 Correct 258 ms 52320 KB Output is correct
57 Correct 148 ms 28688 KB Output is correct
58 Correct 167 ms 28860 KB Output is correct
59 Correct 225 ms 51324 KB Output is correct