oj.uz

Submission #760383

# Submission time Handle Problem Language Result Execution time Memory
760383 2023-06-17T14:23:11 Z GrindMachine Horses (IOI15_horses) C++17
100 / 100
 391 ms 63972 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 ans = 0;
	// 	ll curr = 1;
	// 	rep(i,n){
	// 		curr *= a[i];
	// 		amax(ans, curr * b[i]);
	// 	}

	// 	return 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:237: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]
  237 |  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)
......
  241 |  rep(i,sz(points)-1){
      |      ~~~~~~~~~~~~~~                 
horses.cpp:241:2: note: in expansion of macro 'rep'
  241 |  rep(i,sz(points)-1){
      |  ^~~
horses.cpp:244:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  244 |   ll mxb = st_max.query(l,r).a;
      |                         ^
horses.cpp:244:27: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  244 |   ll mxb = st_max.query(l,r).a;
      |                           ^
horses.cpp:248:34: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
  248 |  ll ans = (best % MOD) * befprod % MOD;
      |           ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:249:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  249 |  return ans;
      |         ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23788 KB Output is correct
2 Correct 9 ms 23764 KB Output is correct
3 Correct 10 ms 23780 KB Output is correct
4 Correct 9 ms 23808 KB Output is correct
5 Correct 9 ms 23800 KB Output is correct
6 Correct 9 ms 23816 KB Output is correct
7 Correct 9 ms 23716 KB Output is correct
8 Correct 9 ms 23812 KB Output is correct
9 Correct 9 ms 23808 KB Output is correct
10 Correct 9 ms 23756 KB Output is correct
11 Correct 9 ms 23764 KB Output is correct
12 Correct 9 ms 23764 KB Output is correct
13 Correct 9 ms 23764 KB Output is correct
14 Correct 9 ms 23796 KB Output is correct
15 Correct 10 ms 23764 KB Output is correct
16 Correct 9 ms 23764 KB Output is correct
17 Correct 8 ms 23764 KB Output is correct
18 Correct 9 ms 23812 KB Output is correct
19 Correct 9 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 8 ms 23804 KB Output is correct
2 Correct 8 ms 23764 KB Output is correct
3 Correct 9 ms 23708 KB Output is correct
4 Correct 9 ms 23764 KB Output is correct
5 Correct 11 ms 23776 KB Output is correct
6 Correct 9 ms 23764 KB Output is correct
7 Correct 8 ms 23764 KB Output is correct
8 Correct 8 ms 23764 KB Output is correct
9 Correct 8 ms 23812 KB Output is correct
10 Correct 9 ms 23720 KB Output is correct
11 Correct 9 ms 23812 KB Output is correct
12 Correct 12 ms 23808 KB Output is correct
13 Correct 9 ms 23728 KB Output is correct
14 Correct 9 ms 23764 KB Output is correct
15 Correct 10 ms 23804 KB Output is correct
16 Correct 9 ms 23816 KB Output is correct
17 Correct 8 ms 23764 KB Output is correct
18 Correct 8 ms 23808 KB Output is correct
19 Correct 12 ms 23764 KB Output is correct
20 Correct 9 ms 23764 KB Output is correct
21 Correct 8 ms 23808 KB Output is correct
22 Correct 9 ms 23760 KB Output is correct
23 Correct 9 ms 23764 KB Output is correct
24 Correct 10 ms 23828 KB Output is correct
25 Correct 9 ms 23792 KB Output is correct
26 Correct 9 ms 23820 KB Output is correct
27 Correct 10 ms 23764 KB Output is correct
28 Correct 13 ms 23848 KB Output is correct
29 Correct 11 ms 23820 KB Output is correct
30 Correct 9 ms 23844 KB Output is correct
31 Correct 9 ms 23784 KB Output is correct
32 Correct 11 ms 23820 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 52076 KB Output is correct
2 Correct 312 ms 52188 KB Output is correct
3 Correct 284 ms 52128 KB Output is correct
4 Correct 391 ms 53532 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23804 KB Output is correct
2 Correct 9 ms 23764 KB Output is correct
3 Correct 8 ms 23772 KB Output is correct
4 Correct 8 ms 23804 KB Output is correct
5 Correct 10 ms 23764 KB Output is correct
6 Correct 9 ms 23704 KB Output is correct
7 Correct 9 ms 23808 KB Output is correct
8 Correct 9 ms 23764 KB Output is correct
9 Correct 8 ms 23764 KB Output is correct
10 Correct 9 ms 23764 KB Output is correct
11 Correct 11 ms 23808 KB Output is correct
12 Correct 10 ms 23796 KB Output is correct
13 Correct 9 ms 23760 KB Output is correct
14 Correct 9 ms 23812 KB Output is correct
15 Correct 9 ms 23816 KB Output is correct
16 Correct 8 ms 23764 KB Output is correct
17 Correct 9 ms 23812 KB Output is correct
18 Correct 8 ms 23764 KB Output is correct
19 Correct 12 ms 23812 KB Output is correct
20 Correct 9 ms 23808 KB Output is correct
21 Correct 8 ms 23764 KB Output is correct
22 Correct 12 ms 23712 KB Output is correct
23 Correct 9 ms 23836 KB Output is correct
24 Correct 11 ms 23764 KB Output is correct
25 Correct 13 ms 23996 KB Output is correct
26 Correct 11 ms 23820 KB Output is correct
27 Correct 13 ms 23820 KB Output is correct
28 Correct 10 ms 23820 KB Output is correct
29 Correct 10 ms 23764 KB Output is correct
30 Correct 10 ms 23780 KB Output is correct
31 Correct 10 ms 23780 KB Output is correct
32 Correct 10 ms 23828 KB Output is correct
33 Correct 101 ms 29336 KB Output is correct
34 Correct 99 ms 29296 KB Output is correct
35 Correct 222 ms 52596 KB Output is correct
36 Correct 215 ms 52492 KB Output is correct
37 Correct 103 ms 29220 KB Output is correct
38 Correct 146 ms 41076 KB Output is correct
39 Correct 93 ms 29112 KB Output is correct
40 Correct 217 ms 57172 KB Output is correct
41 Correct 93 ms 29772 KB Output is correct
42 Correct 98 ms 30052 KB Output is correct
43 Correct 211 ms 57552 KB Output is correct
44 Correct 198 ms 57536 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23744 KB Output is correct
2 Correct 9 ms 23764 KB Output is correct
3 Correct 8 ms 23764 KB Output is correct
4 Correct 11 ms 23816 KB Output is correct
5 Correct 8 ms 23812 KB Output is correct
6 Correct 8 ms 23764 KB Output is correct
7 Correct 8 ms 23764 KB Output is correct
8 Correct 9 ms 23732 KB Output is correct
9 Correct 9 ms 23728 KB Output is correct
10 Correct 9 ms 23724 KB Output is correct
11 Correct 8 ms 23768 KB Output is correct
12 Correct 8 ms 23780 KB Output is correct
13 Correct 9 ms 23764 KB Output is correct
14 Correct 9 ms 23808 KB Output is correct
15 Correct 9 ms 23804 KB Output is correct
16 Correct 9 ms 23752 KB Output is correct
17 Correct 9 ms 23764 KB Output is correct
18 Correct 8 ms 23764 KB Output is correct
19 Correct 9 ms 23724 KB Output is correct
20 Correct 9 ms 23788 KB Output is correct
21 Correct 9 ms 23812 KB Output is correct
22 Correct 9 ms 23792 KB Output is correct
23 Correct 10 ms 23840 KB Output is correct
24 Correct 11 ms 23892 KB Output is correct
25 Correct 10 ms 23816 KB Output is correct
26 Correct 10 ms 23816 KB Output is correct
27 Correct 10 ms 23792 KB Output is correct
28 Correct 10 ms 23812 KB Output is correct
29 Correct 9 ms 23816 KB Output is correct
30 Correct 9 ms 23816 KB Output is correct
31 Correct 9 ms 23824 KB Output is correct
32 Correct 10 ms 23804 KB Output is correct
33 Correct 263 ms 53544 KB Output is correct
34 Correct 311 ms 53376 KB Output is correct
35 Correct 298 ms 53496 KB Output is correct
36 Correct 346 ms 53576 KB Output is correct
37 Correct 101 ms 29412 KB Output is correct
38 Correct 102 ms 29220 KB Output is correct
39 Correct 221 ms 52520 KB Output is correct
40 Correct 224 ms 52556 KB Output is correct
41 Correct 100 ms 29244 KB Output is correct
42 Correct 149 ms 41128 KB Output is correct
43 Correct 94 ms 29036 KB Output is correct
44 Correct 205 ms 57196 KB Output is correct
45 Correct 93 ms 29764 KB Output is correct
46 Correct 97 ms 29860 KB Output is correct
47 Correct 213 ms 57480 KB Output is correct
48 Correct 196 ms 57568 KB Output is correct
49 Correct 161 ms 34868 KB Output is correct
50 Correct 150 ms 34788 KB Output is correct
51 Correct 287 ms 63972 KB Output is correct
52 Correct 258 ms 63460 KB Output is correct
53 Correct 200 ms 33084 KB Output is correct
54 Correct 216 ms 46716 KB Output is correct
55 Correct 134 ms 30764 KB Output is correct
56 Correct 256 ms 58916 KB Output is correct
57 Correct 150 ms 31568 KB Output is correct
58 Correct 163 ms 31952 KB Output is correct
59 Correct 207 ms 57560 KB Output is correct