oj.uz

답안 #753207

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753207 2023-06-04T19:59:48 Z Zflop Happiness (Balkan15_HAPPINESS) C++14
40 / 100
 862 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)1e5 * 64];
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;
		}
	int 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;
	int 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 94 ms 250700 KB Output is correct
2 Correct 93 ms 250736 KB Output is correct
3 Correct 92 ms 250784 KB Output is correct
4 Correct 106 ms 250776 KB Output is correct
5 Correct 98 ms 250704 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 250700 KB Output is correct
2 Correct 93 ms 250736 KB Output is correct
3 Correct 92 ms 250784 KB Output is correct
4 Correct 106 ms 250776 KB Output is correct
5 Correct 98 ms 250704 KB Output is correct
6 Runtime error 252 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 250700 KB Output is correct
2 Correct 93 ms 250736 KB Output is correct
3 Correct 92 ms 250784 KB Output is correct
4 Correct 106 ms 250776 KB Output is correct
5 Correct 98 ms 250704 KB Output is correct
6 Correct 579 ms 251784 KB Output is correct
7 Correct 622 ms 254772 KB Output is correct
8 Correct 623 ms 254908 KB Output is correct
9 Correct 812 ms 256360 KB Output is correct
10 Correct 862 ms 256444 KB Output is correct
11 Correct 311 ms 254620 KB Output is correct
12 Correct 330 ms 254992 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 250700 KB Output is correct
2 Correct 93 ms 250736 KB Output is correct
3 Correct 92 ms 250784 KB Output is correct
4 Correct 106 ms 250776 KB Output is correct
5 Correct 98 ms 250704 KB Output is correct
6 Runtime error 252 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -