Submission #409714

#TimeUsernameProblemLanguageResultExecution timeMemory
409714codebuster_10Happiness (Balkan15_HAPPINESS)C++17
60 / 100
1202 ms524288 KiB
#include <bits/stdc++.h> using namespace std ; #define int int64_t //be careful about this #define endl "\n" #define f(i,a,b) for(int i=int(a);i<int(b);++i) #define pr pair #define ar array #define fr first #define sc second #define vt vector #define pb push_back #define eb emplace_back #define LB lower_bound #define UB upper_bound #define PQ priority_queue #define sz(x) ((int)(x).size()) #define all(a) (a).begin(),(a).end() #define allr(a) (a).rbegin(),(a).rend() #define mem0(a) memset(a, 0, sizeof(a)) #define mem1(a) memset(a, -1, sizeof(a)) template<class A> void rd(vt<A>& v); template<class T> void rd(T& x){ cin >> x; } template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;} template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;} template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } /* Description :- Sparse lazy segment tree Source :- https://usaco.guide/plat/sparse-seg?lang=cpp Verification :- https://oj.uz/submission/409297 */ struct Node { int sum, tl, tr, l, r;// node cover [tl,tr], also lazy is not added to current node; Node() : sum(0), l(-1), r(-1) {} }; const int BEST = 7e6; Node st[BEST]; int cnt = 2; void update(int x, int l, int r, int val) { if (l == st[x].tl && r == st[x].tr) { st[x].sum += val; assert(l == r); } else { int mid = (st[x].tl + st[x].tr) / 2; if (st[x].l == -1) { st[x].l = cnt++; st[st[x].l].tl = st[x].tl; st[st[x].l].tr = mid; } if (st[x].r == -1) { st[x].r = cnt++; st[st[x].r].tl = mid + 1; st[st[x].r].tr = st[x].tr; } if (l > mid) update(st[x].r, l, r, val); else if (r <= mid) update(st[x].l, l, r, val); else { update(st[x].l, l, mid, val); update(st[x].r, mid + 1, r, val); } st[x].sum = st[st[x].l].sum + st[st[x].r].sum; } } int query(int x, int l, int r) { if (l <= st[x].tl && st[x].tr <= r) return st[x].sum; else { int mid = (st[x].tl + st[x].tr) / 2; if (st[x].l == -1) { st[x].l = cnt++; st[st[x].l].tl = st[x].tl; st[st[x].l].tr = mid; } if (st[x].r == -1) { st[x].r = cnt++; st[st[x].r].tl = mid + 1; st[st[x].r].tr = st[x].tr; } if (l > mid) return query(st[x].r, l, r); else if (r <= mid) return query(st[x].l, l, r); else return query(st[x].l, l, r) + query(st[x].r, l, r); } } int W; bool go(){ for(int x = 1; x < W;){ int res = query(1,1,x); if(res < x){ return false; } x = res + 1; } return true; } #undef int bool init(int coinsCount, long long maxCoinSize, long long coins[]) { #define int int64_t int n = coinsCount, M = maxCoinSize; //rd(n,M); st[1].tl = 1, st[1].tr = M; f(i,0,n){ update(1,coins[i],coins[i],coins[i]); W += coins[i]; } return go(); } #undef int bool is_happy(int event, int coinsCount, long long coins[]) { #define int int64_t int t = event; if(t == -1){ int N = coinsCount; f(i,0,N){ update(1,coins[i],coins[i],-coins[i]); W -= coins[i]; } }else{ int N = coinsCount; f(i,0,N){ update(1,coins[i],coins[i],coins[i]); W += coins[i]; } } return go(); #undef int } /* #define NMAX 200000 #define QMAX 100000 static int N, Q; static long long M; static long long coins[NMAX], A[5]; int main() { int i, d; long long max_code; scanf("%d%lld", &N, &M); for (i = 0; i < N; ++i) { scanf("%lld", &coins[i]); } if (init(N, M, coins))printf("1\n"); else printf("0\n"); scanf("%d", &Q); for (i = 0; i < Q; ++i) { int ck, c; scanf("%d%d", &ck, &c); for (int j = 0; j < c; j++) { scanf("%lld", &A[j]); } if (is_happy(ck, c, A))printf("1\n"); else printf("0\n"); } return 0; }*/

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...