oj.uz

Submission #753212

# Submission time Handle Problem Language Result Execution time Memory
753212 2023-06-04T20:05:52 Z Zflop Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1643 ms 322384 KB 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

//#include "happiness.h"

/*
ID: 10002181
LANG: C++
TASK: lamps
*/
 
using str = string; // yay python!
using ld = long double; // or double, if TL is tight
using ll = long long;
using int64 = ll;
using db = double;
using ull = unsigned long long;
 
#define ch() getchar()
#define pc(x) putchar(x)
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vpi = V<pair<int,int>>;
using vvi = V<vi>;
using vl = V<ll>;
using vd = V<ld>;
using vstr = V<str>;
 
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rev(x) reverse(all(x))
#define sz(x) (int)(x).size()
#define rall(x) x.rbegin(), x.rend()
#define AR array
 
// loops
#define F0R(i, a, b) for (int i=a; i<b;++i)
#define FOR(i, a) for (int i=0; i<a;++i)
#define FORn(i, a) for (int i=1; i<=a;++i)
#define ROF(i,a) for(int i=a-1; i >= 0;--i)
#define R0F(i,a,b) for(int i=a; i > b;--i)
#define ROFn(i,a) for(int i=a; i > 0;--i)
#define rep(a) FOR(_, a)
#define trav(i,x) for(auto& i:x)
 
// pairs
#define mp make_pair
#define pi pair <int, int>
#define f first
#define s second
 
// vectors
#define lb lower_bound
#define ub upper_bound
#define SUM(v) accumulate(all(v), 0LL)
#define MN(v) *min_element(all(v))
#define MX(v) *max_element(all(v))
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define eb emplace_back
#define ft front()
#define bk back()
#define ins insert
#define pf push_front
#define pb push_back
#define emt empty()
#define rsz resize
 
#define pob pop_back()
#define pof pop_front()
 
#define ts to_string
 
#define setIO()  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
 
ll MOD = 1e9+7;
const ll MAX = 100000000000;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
 
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
 
tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }
 
tcTU> T fstTrue(T lo, T hi, U f) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true
		T mid = lo+(hi-lo)/2;
		f(mid) ? hi = mid : lo = mid+1;
	}
	return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true
		T mid = lo+(hi-lo+1)/2;
		f(mid) ? lo = mid : hi = mid-1;
	}
	return lo;
}
 
//INPUT
#define tcTUU tcT, class ...U
tcT> void re(complex<T>& c);
tcTU> void re(pair<T,U>& p);
tcT> void re(V<T>& v);
tcT, size_t SZ> void re(AR<T,SZ>& a);
 
tcT> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }
 
tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; }
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> void re(V<T>& x) { trav(a,x) re(a); }
tcT> void rv(int n, V<T>& x) { x.rsz(n); re(x); }
 
//OUTPUT
namespace output {
	tcT> void PS(V<T>& x) { FOR(i,sz(x)) cout << x[i] << " \n"[i + 1 == sz(x)];}
	tcT> void W(pair<T,T>& x) { cout << x.f << ' ' << x.s << '\n'; }
	tcT> void PS(bool ok) { if(ok) cout << "YES\n"; else cout << "NO\n"; }
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    tcT, size_t SZ> void pr(const array<T,SZ>& x);
    tcT> void pr(const vector<T>& x);
    tcT> void pr(const set<T>& x);
    template<class T1, class T2> void pr(const map<T1,T2>& x);
 
    tcT> void pr(const T& x) { cout << x; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
        pr(first); pr(rest...);
    }
 
    template<class T1, class T2> void pr(const pair<T1,T2>& x) {
        pr("{",x.f,", ",x.s,"}");
    }
    tcT> void prContain(const T& x) {
        pr("{");
        bool fst = 1; trav(a,x) pr(!fst?", ":"",a), fst = 0;
        pr("}");
    }
    tcT, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
    tcT> void pr(const vector<T>& x) { prContain(x); }
    tcT> void pr(const set<T>& x) { prContain(x); }
    template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
 
    void ps() { pr("\n"); } // print w/ spaces
    template<class Arg> void ps(const Arg& first) { pr(first,"\n"); }
    template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
        pr(first," "); ps(rest...);
    }
}
 
using namespace output;
 
template<class T,class V> void add(T& a, const V& b) {
	a = (a + b) % MOD;
	}
template<class T,class V> void sub(T& a, const V& b) {
	a = (a - b + MOD) % MOD;
	}
template<class T,class V> void mult(T& a, const V& b) {
	a = a * b % MOD;
	}
 
void setF(string fileName = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if((int)fileName.size()) {
		freopen((fileName+".in").c_str(), "r", stdin);
		freopen((fileName+".out").c_str(), "w", stdout);
	}
}
 
 
vb bb;
vi SIEVE(int N){ // sieve in O(N logN)
	vi pr;
	bb.rsz(N);
	bb[0] = bb[1] = true;
	vi g(N);
	F0R(i,2,N){
		if(!bb[i]){
			pr.pb(i);
			for (int j = i + i; j < N; j += i) bb[j] = true;
			}
		}
	return pr;
	}
 
 
 
template<class T> using ordset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
struct edge{
	int a;
	int b;
	int w;
	};
 
ll POW(ll x, ll y,ll mod){
    ll res = 1LL;
    x %= mod;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}
 
ll fact(ll x) { if(x) return x * fact(x - 1ll); return 1; }
 
vl fc;
void F(int N,ll MOD){
	fc.rsz(N + 1);
	fc[0] = 1;
	FORn(i,N) fc[i] = fc[i - 1] * i * 1ll % MOD;
	}
 
vl inv;
void I(int N,ll MOD){
	inv.rsz(N + 1);
	inv[N] = POW(fc[N],MOD - 2,MOD);
	for (int i = N; i ;--i) inv[i - 1] = inv[i] * 1ll * i % MOD;
	}
 
ll Cr(ll N,ll K,ll mod){
	if(K < 0) return 0;
	if(K > N) return 0;
	return fc[N] * 1ll * inv[K] % mod * inv[N - K] % mod;
	}
ll Ar(ll N,ll K,ll mod){
	return fc[N] * inv[N - K] % mod;
	}
ll iv(int k,ll MOD){
  return POW(k,MOD-2,MOD);
}
 
/*
 scanf("%lld", &testInteger);
 printf("%lld", testInteger);
 
 ____ ____ ____ ____ ____  ____
||f |||l |||o |||p |||p ||||y ||
||__|||__|||__|||__|||__||||__||
|/__\|/__\|/__\|/__\|/__\||/__\|
 
**/
struct Node{
	ll sm,tl,tr,l,r;
	Node() : sm(0),tl(-1),tr(-1) {}
	};
Node C[(int)1e6 * 8];
int x;


void add(int node,ll v,ll l,ll r){
	if(r < C[node].l || C[node].r < l) return;
	if(l <= C[node].l && C[node].r <= r){
		C[node].sm += v;
		return;
		}
	ll mid = (C[node].l + C[node].r) / 2;
	if(l > mid) {
		if(C[node].tr == -1){
			C[node].tr = ++x;
			C[x].l = mid + 1;
			C[x].r = C[node].r;
			}
		add(C[node].tr,v,l,r);
		}
	else {
		if(C[node].tl == -1){
			C[node].tl = ++x;
			C[x].l = C[node].l;
			C[x].r = mid;
			}
		add(C[node].tl,v,l,r);
		}
	C[node].sm = C[C[node].tl].sm + C[C[node].tr].sm;
	}
ll query(int node,ll l,ll r){
	if(r < C[node].l || C[node].r < l) return 0;
	if(l <= C[node].l && C[node].r <= r) return C[node].sm;
	ll mid = (C[node].l + C[node].r) / 2;
	if(C[node].tr == -1) {
		C[node].tr = ++x;
		C[x].l = mid + 1;
		C[x].r = C[node].r;
		}
	if(C[node].tl == -1) {
		C[node].tl = ++x;
		C[x].l = C[node].l;
		C[x].r = mid;
		}
	return query(C[node].tr,l,r) + query(C[node].tl,l,r);
	}

bool check(){
	ll t = 1;
	ll sm = query(0,1,C[0].r);
	while (t < sm){
		ll a = query(0,1,t);
		//ps(t,a);
		if(a < t) return false;
		t = a + 1; 
		}
	return true;
	}

bool init(int coinsCount, long long maxCoinSize, long long coins[]){
	C[0].l = 1;
	C[0].r = maxCoinSize;
	for (int i = 0; i < coinsCount;++i){
		add(0,coins[i],coins[i],coins[i]);
		}
	return check();
	}
bool is_happy(int event, int coinsCount, long long coins[]){
	for (int i = 0; i < coinsCount;++i){
		add(0,coins[i] * event,coins[i],coins[i]);
		}
	return check();
	}

Compilation message

happiness.cpp: In function 'void setF(std::string)':
happiness.cpp:184:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |   freopen((fileName+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
happiness.cpp:185:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |   freopen((fileName+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 313360 KB Output is correct
2 Correct 122 ms 313420 KB Output is correct
3 Correct 118 ms 313424 KB Output is correct
4 Correct 113 ms 313320 KB Output is correct
5 Correct 118 ms 313376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 313360 KB Output is correct
2 Correct 122 ms 313420 KB Output is correct
3 Correct 118 ms 313424 KB Output is correct
4 Correct 113 ms 313320 KB Output is correct
5 Correct 118 ms 313376 KB Output is correct
6 Correct 122 ms 313412 KB Output is correct
7 Correct 116 ms 313340 KB Output is correct
8 Correct 147 ms 313432 KB Output is correct
9 Correct 166 ms 313416 KB Output is correct
10 Correct 150 ms 313380 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 313360 KB Output is correct
2 Correct 122 ms 313420 KB Output is correct
3 Correct 118 ms 313424 KB Output is correct
4 Correct 113 ms 313320 KB Output is correct
5 Correct 118 ms 313376 KB Output is correct
6 Correct 584 ms 314480 KB Output is correct
7 Correct 588 ms 314548 KB Output is correct
8 Correct 630 ms 314316 KB Output is correct
9 Correct 821 ms 314324 KB Output is correct
10 Correct 759 ms 314392 KB Output is correct
11 Correct 317 ms 313588 KB Output is correct
12 Correct 295 ms 313552 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 313360 KB Output is correct
2 Correct 122 ms 313420 KB Output is correct
3 Correct 118 ms 313424 KB Output is correct
4 Correct 113 ms 313320 KB Output is correct
5 Correct 118 ms 313376 KB Output is correct
6 Correct 122 ms 313412 KB Output is correct
7 Correct 116 ms 313340 KB Output is correct
8 Correct 147 ms 313432 KB Output is correct
9 Correct 166 ms 313416 KB Output is correct
10 Correct 150 ms 313380 KB Output is correct
11 Correct 584 ms 314480 KB Output is correct
12 Correct 588 ms 314548 KB Output is correct
13 Correct 630 ms 314316 KB Output is correct
14 Correct 821 ms 314324 KB Output is correct
15 Correct 759 ms 314392 KB Output is correct
16 Correct 317 ms 313588 KB Output is correct
17 Correct 295 ms 313552 KB Output is correct
18 Correct 1334 ms 314340 KB Output is correct
19 Correct 1382 ms 314436 KB Output is correct
20 Correct 1643 ms 322384 KB Output is correct
21 Correct 997 ms 319360 KB Output is correct
22 Correct 426 ms 319308 KB Output is correct
23 Correct 461 ms 319816 KB Output is correct
24 Correct 1267 ms 319696 KB Output is correct