oj.uz

Submission #707604

# Submission time Handle Problem Language Result Execution time Memory
707604 2023-03-09T13:28:37 Z baojiaopisu Horses (IOI15_horses) C++14
100 / 100
 456 ms 55072 KB 
#include<bits/stdc++.h>
#include "horses.h"
 
using namespace std;
 
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
 
#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz
 
#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
 
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }
 
const int MOD = 1e9 + 7; //998244353
 
template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}
 
template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}
 
/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/
 
const ll INF = 1e9;
const int N = 5e5 + 10;
 
template <typename T> T mod_inv_in_range(T a, T m) {
    // assert(0 <= a && a < m);
    T x = a, y = m;
    T vx = 1, vy = 0;
    while (x) {
        T k = y / x;
        y %= x;
        vy -= k * vx;
        std::swap(x, y);
        std::swap(vx, vy);
    }
    assert(y == 1);
    return vy < 0 ? m + vy : vy;
}
 
template <typename T> T mod_inv(T a, T m) {
    a %= m;
    a = a < 0 ? a + m : a;
    return mod_inv_in_range(a, m);
}
 
template <int MOD_> struct modnum {
    static constexpr int MOD = MOD_;
    static_assert(MOD_ > 0, "MOD must be positive");
 
    using ll = long long;
 
    int v;
 
public:
 
    modnum() : v(0) {}
    modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
    explicit operator int() const { return v; }
    friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
    friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
 
    friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
    friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
 
    modnum inv() const {
        modnum res;
        res.v = mod_inv_in_range(v, MOD);
        return res;
    }
    friend modnum inv(const modnum& m) { return m.inv(); }
    modnum neg() const {
        modnum res;
        res.v = v ? MOD-v : 0;
        return res;
    }
    friend modnum neg(const modnum& m) { return m.neg(); }
 
    modnum operator- () const {
        return neg();
    }
    modnum operator+ () const {
        return modnum(*this);
    }
 
    modnum& operator ++ () {
        v ++;
        if (v == MOD) v = 0;
        return *this;
    }
    modnum& operator -- () {
        if (v == 0) v = MOD;
        v --;
        return *this;
    }
    modnum& operator += (const modnum& o) {
        v -= MOD-o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum& operator -= (const modnum& o) {
        v -= o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum& operator *= (const modnum& o) {
        v = int(ll(v) * ll(o.v) % MOD);
        return *this;
    }
    modnum& operator /= (const modnum& o) {
        return *this *= o.inv();
    }
 
    friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
    friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
    friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
    friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
    friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
    friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
using num = modnum<MOD>;
 
template <class T> struct FenwickTree {
	int n;
	vector<T> bit;
 
	FenwickTree(int _n = 0) {
		n = _n;
		bit.resize(n + 5);
		for(int i = 1; i <= n; i++) bit[i] = 1;
	}
 
	void update(int pos, T x) {
		for(int i = pos; i <= n; i += i & (-i)) bit[i] *= x;
	}
 
	T get(int pos) {
		T ans = 1;
		for(int i = pos; i > 0; i -= i & (-i)) ans *= bit[i];
		return ans;
	}
};
 
struct SegTree {
	int n;
	vector<int> node;
 
	SegTree(int _n = 0) {
		n = _n;
		node.resize(4 * n + 7);
	}
 
private:
	void Update(int l, int r, int pos, int val, int id) {
		if(l == r) {
			node[id] = val;
			return;
		}
 
		int mid = (l + r) >> 1;
		if(pos <= mid) Update(l, mid, pos, val, id << 1);
		else Update(mid + 1, r, pos, val, id << 1 | 1);
		node[id] = max(node[id << 1], node[id << 1 | 1]);
	}
 
	int Get(int l, int r, int lo, int hi, int id) {
		if(l > hi || r < lo) return 0;
		if(lo <= l && r <= hi) return node[id];
 
		int mid = (l + r) >> 1;
		int left = Get(l, mid, lo, hi, id << 1);
		int right = Get(mid + 1, r, lo, hi, id << 1 | 1);
		return max(left, right);	
	}
 
public:
	void update(int pos, int val) {
		Update(1, n, pos, val, 1);
	}
 
	int get(int l, int r) {
		return Get(1, n, l, r, 1);
	}
};
SegTree IT = SegTree(10);
FenwickTree<num> BIT;
set<int> curr;
int x[N], y[N], n;
 
int calc() {
	int pos = n;
	auto iter = curr.end(); iter = prev(iter);
	ll r = 0;
	int ans = 0;
	while(true) {
		int t = (*iter);
 
		int v = IT.get(t, pos);
		if(v > r) {
			r = v;
			int cc = BIT.get(t).v;
			ans = 1ll * cc * v % MOD;
		}
		pos = t - 1;
 
		r = r * x[(*iter)];
		if(r > INF) break;
		if(iter == curr.begin()) break;
		iter = prev(iter);
	}
 
	return ans;
}
 
int init(int N, int X[], int Y[]) {
	n = N;
	for(int i = n; i >= 1; i--) {
		x[i] = X[i - 1];
		y[i] = Y[i - 1];
	}
 
	IT = SegTree(n); BIT = FenwickTree<num>(n);
 
	curr.ins(1);
	for(int i = 1; i <= n; i++) {
		IT.update(i, y[i]);
		BIT.update(i, x[i]);
		if(x[i] > 1) curr.ins(i);
	}
 
	return calc();
}
 
int updateX(int pos, int val) {
	pos++;
	if(x[pos] > 1) curr.erase(pos);
	BIT.update(pos, num(1) / num(x[pos]));
	x[pos] = val;
	if(x[pos] > 1) curr.ins(pos);
	if(x[1] == 1) curr.ins(1);
	BIT.update(pos, x[pos]);
	return calc();
}
 
int updateY(int pos, int val) {
	++pos;
	y[pos] = val;
	IT.update(pos, y[pos]);
	return calc();
}

Compilation message

horses.cpp: In function 'int calc()':
horses.cpp:249:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  249 |    ans = 1ll * cc * v % MOD;
      |          ~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:262:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  262 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:71:11: note: shadowed declaration is here
   71 | const int N = 5e5 + 10;
      |           ^

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 43976 KB Output is correct
2 Correct 322 ms 55072 KB Output is correct
3 Correct 317 ms 46164 KB Output is correct
4 Correct 344 ms 49952 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct
33 Correct 79 ms 18052 KB Output is correct
34 Correct 82 ms 22092 KB Output is correct
35 Correct 227 ms 52412 KB Output is correct
36 Correct 226 ms 52204 KB Output is correct
37 Correct 107 ms 20236 KB Output is correct
38 Correct 137 ms 32932 KB Output is correct
39 Correct 74 ms 19972 KB Output is correct
40 Correct 224 ms 47364 KB Output is correct
41 Correct 90 ms 19972 KB Output is correct
42 Correct 98 ms 20108 KB Output is correct
43 Correct 217 ms 47820 KB Output is correct
44 Correct 224 ms 47752 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct
33 Correct 451 ms 44108 KB Output is correct
34 Correct 329 ms 54976 KB Output is correct
35 Correct 324 ms 46332 KB Output is correct
36 Correct 366 ms 50000 KB Output is correct
37 Correct 84 ms 22024 KB Output is correct
38 Correct 82 ms 21964 KB Output is correct
39 Correct 261 ms 52348 KB Output is correct
40 Correct 225 ms 52300 KB Output is correct
41 Correct 104 ms 20224 KB Output is correct
42 Correct 136 ms 32928 KB Output is correct
43 Correct 75 ms 19992 KB Output is correct
44 Correct 234 ms 47308 KB Output is correct
45 Correct 94 ms 19984 KB Output is correct
46 Correct 97 ms 20032 KB Output is correct
47 Correct 196 ms 47784 KB Output is correct
48 Correct 203 ms 47788 KB Output is correct
49 Correct 143 ms 25012 KB Output is correct
50 Correct 145 ms 24972 KB Output is correct
51 Correct 314 ms 54192 KB Output is correct
52 Correct 265 ms 53664 KB Output is correct
53 Correct 429 ms 23372 KB Output is correct
54 Correct 233 ms 36944 KB Output is correct
55 Correct 137 ms 20980 KB Output is correct
56 Correct 289 ms 49100 KB Output is correct
57 Correct 276 ms 21580 KB Output is correct
58 Correct 379 ms 22164 KB Output is correct
59 Correct 214 ms 47744 KB Output is correct