oj.uz

답안 #753209

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753209 2023-06-04T20:02:01 Z Zflop Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1131 ms 524288 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 * 7];
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(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;
		}
	add(C[node].tr,v,l,r);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 274252 KB Output is correct
2 Correct 97 ms 274164 KB Output is correct
3 Correct 101 ms 274244 KB Output is correct
4 Correct 102 ms 274252 KB Output is correct
5 Correct 102 ms 274180 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 274252 KB Output is correct
2 Correct 97 ms 274164 KB Output is correct
3 Correct 101 ms 274244 KB Output is correct
4 Correct 102 ms 274252 KB Output is correct
5 Correct 102 ms 274180 KB Output is correct
6 Correct 111 ms 274152 KB Output is correct
7 Correct 104 ms 274164 KB Output is correct
8 Correct 143 ms 274428 KB Output is correct
9 Correct 145 ms 274452 KB Output is correct
10 Correct 130 ms 274392 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 274252 KB Output is correct
2 Correct 97 ms 274164 KB Output is correct
3 Correct 101 ms 274244 KB Output is correct
4 Correct 102 ms 274252 KB Output is correct
5 Correct 102 ms 274180 KB Output is correct
6 Correct 640 ms 275272 KB Output is correct
7 Correct 568 ms 275324 KB Output is correct
8 Correct 615 ms 275164 KB Output is correct
9 Correct 773 ms 275160 KB Output is correct
10 Correct 772 ms 275348 KB Output is correct
11 Correct 315 ms 274488 KB Output is correct
12 Correct 308 ms 274524 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 274252 KB Output is correct
2 Correct 97 ms 274164 KB Output is correct
3 Correct 101 ms 274244 KB Output is correct
4 Correct 102 ms 274252 KB Output is correct
5 Correct 102 ms 274180 KB Output is correct
6 Correct 111 ms 274152 KB Output is correct
7 Correct 104 ms 274164 KB Output is correct
8 Correct 143 ms 274428 KB Output is correct
9 Correct 145 ms 274452 KB Output is correct
10 Correct 130 ms 274392 KB Output is correct
11 Correct 640 ms 275272 KB Output is correct
12 Correct 568 ms 275324 KB Output is correct
13 Correct 615 ms 275164 KB Output is correct
14 Correct 773 ms 275160 KB Output is correct
15 Correct 772 ms 275348 KB Output is correct
16 Correct 315 ms 274488 KB Output is correct
17 Correct 308 ms 274524 KB Output is correct
18 Runtime error 1131 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -