oj.uz

답안 #287519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287519 2020-08-31T18:33:00 Z jainbot27 Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 1970 ms 67448 KB 
//author: JainBot27
//Created on: 08/31/20
#pragma GCC optimize("Ofast")
#pragma GCC target("sse4,avx,avx2,fma")
#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;


#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ts to_string
#define ub upper_bound
#define lb lower_bound
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, y, z) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, z, 0)
#define trav(x, y) for(auto&x:y)


const string nl = "\n";
using ll = int64_t;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using vpii = vector<pii>;
using vpll = vector<pll>;


template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
template<class A> str ts(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) { 
    str res = "{"; for(int i = 0;i < (int)v.size(); i++) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; for(int i = 0; i < b.size(); i++) res += char('0'+b[i]);
    return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { 
    bool fst = 1; str res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
    return "("+ts(p.f)+", "+ts(p.s)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << ts(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }


#ifdef D 
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
using node = ll;

struct lazy{
    int size;
    vector<node> operations;
    vector<node> vals;
    const node NEUTRAL_ELEMENT = 1e18;
    const node NO_OPERATION = 0;
    const node START_VAL = 0;
    ll query_op(node a, node b, int len){
        len = len;
        return (a + b);
    }
    ll calc_op(node a, node b){
        return min(a, b);
    }
    void apply_mod_op(node & a, node b, int c){
        a = query_op(a, b, c);
    }
    void propogate(int x, int lx, int rx){
        if(rx - lx == 1) return;
        int m = (lx + rx)/2;
        apply_mod_op(operations[2*x+1], operations[x], 1);
        apply_mod_op(vals[2*x+1], operations[x], m-lx);
        apply_mod_op(operations[2*x+2], operations[x], 1);
        apply_mod_op(vals[2*x+2], operations[x], rx-m);
        operations[x] = NO_OPERATION;
    }
    void build(int x, int lx, int rx){
        if(rx == lx + 1){
            vals[x] = START_VAL;
            return;
        }
        int m = (lx + rx)/2;
        build(2*x + 1, lx, m);
        build(2*x + 2, m, rx);
        vals[x] = calc_op(vals[x * 2 + 1], vals[x * 2 + 2]);
    }
    void init(int n){
        size = 1;
        while(size < n) size *= 2;
        operations.assign(2 * size, 0);
        vals.assign(2 * size, 0);
        // build(0, 0, size);
    }
    void update(int l, int r, node v, int x, int lx, int rx){
        propogate(x, lx, rx);
        if(lx >= r || l >= rx) return;
        if(lx >= l && rx <= r){
            apply_mod_op(operations[x], v, 1);
            apply_mod_op(vals[x], v, rx - lx);
            return;
        }
        int m = (lx + rx)/2;
        update(l, r, v, 2 * x + 1, lx , m);
        update(l, r, v, 2 * x + 2, m , rx);
        vals[x] = calc_op(vals[x * 2 + 1], vals[x * 2 + 2]);
    }
    void update(int l, int r, node v){
        update(l, r, v, 0, 0, size);
    }
    node query(int l, int r, int x, int lx, int rx){
        propogate(x, lx, rx);
        if(lx >= r || l >= rx) return NEUTRAL_ELEMENT;
        if(lx >= l && rx <= r){
            return vals[x];
        }
        int m = (lx + rx)/2;
        node m1 = query(l, r, 2 * x + 1, lx, m);
        node m2 = query(l, r, 2 * x + 2, m, rx);
        return calc_op(m1, m2);
    }
    node query(int l , int r){
        return query(l, r, 0, 0, size);
    }
} st;
multiset<int> e;
bool init(int coinsCount, long long maxCoinSize, long long coins[]){
    st.init(1000001);
    //assert(maxCoinSize<=1000001);
    FOR(i, 1, 1000001){
        st.update(i, i+1, -i);
    }
    F0R(i, coinsCount){
        st.update(coins[i],1000001,coins[i]);
        e.insert(coins[i]);
    }
    //return (st.query(1, *(e.rbegin())+1)>=0?"YES":"NO") << nl;
    if(e.size())
        return st.query(1, *(e.rbegin())+1)>=0;
    else
        return 1;
}
bool is_happy(int event, int coinsCount, long long coins[]){
    //return 0;
    dbg(event);
    F0R(i, coinsCount){
        int x; x = coins[i];
        x*=event;
        dbg(x);
        if(x < 0){ 
            //assert(e.find(-x) != e.end());
            e.erase(e.find(-x));
        }
        else e.insert((x));
        if(x < 0){
            st.update(-x, 1000001, x);
        }
        else{
            st.update(x, 1000001, x);
        }
    }
    if(e.size())
        return st.query(1, *(e.rbegin())+1)>=0;
    else
        return 1;
}

/*
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    long long x[] = {4,8,1,2,6};
    cout << (init(5, 100, x)?"YES":"NO")<< nl; 
    long long y[] = {2, 8};
    cout << (is_happy(-1, 2, y)?"YES":"NO")<< nl; 
    long long z[] = {7, 9, 2};
    cout << (is_happy(1, 2, y)?"YES":"NO")<< nl; 
}
/*
 * Stuff I should try:
 * Is it Monotonic? -> Binary Search
 * Is N small? -> Bitsets or other exponential
 * Edge Cases? Look Carefully 
 * Can't figure anything out? Brute Force and see patterns
 * Try to prove greedies
 * Prefix Sums, Amortization, DP, Data Structures
*/

Compilation message

happiness.cpp:205:1: warning: "/*" within comment [-Wcomment]
  205 | /*
      |  
happiness.cpp: In function 'bool is_happy(int, int, long long int*)':
happiness.cpp:75:18: warning: statement has no effect [-Wunused-value]
   75 | #define dbg(...) 0
      |                  ^
happiness.cpp:172:5: note: in expansion of macro 'dbg'
  172 |     dbg(event);
      |     ^~~
happiness.cpp:75:18: warning: statement has no effect [-Wunused-value]
   75 | #define dbg(...) 0
      |                  ^
happiness.cpp:176:9: note: in expansion of macro 'dbg'
  176 |         dbg(x);
      |         ^~~
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 403 ms 33152 KB Output is correct
2 Correct 404 ms 33400 KB Output is correct
3 Correct 404 ms 33232 KB Output is correct
4 Correct 406 ms 33228 KB Output is correct
5 Correct 402 ms 33272 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 403 ms 33152 KB Output is correct
2 Correct 404 ms 33400 KB Output is correct
3 Correct 404 ms 33232 KB Output is correct
4 Correct 406 ms 33228 KB Output is correct
5 Correct 402 ms 33272 KB Output is correct
6 Runtime error 448 ms 67448 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 403 ms 33152 KB Output is correct
2 Correct 404 ms 33400 KB Output is correct
3 Correct 404 ms 33232 KB Output is correct
4 Correct 406 ms 33228 KB Output is correct
5 Correct 402 ms 33272 KB Output is correct
6 Correct 1303 ms 42120 KB Output is correct
7 Correct 1269 ms 42092 KB Output is correct
8 Correct 1296 ms 42268 KB Output is correct
9 Correct 1791 ms 43476 KB Output is correct
10 Correct 1970 ms 46092 KB Output is correct
11 Correct 1130 ms 46584 KB Output is correct
12 Correct 1117 ms 46712 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 403 ms 33152 KB Output is correct
2 Correct 404 ms 33400 KB Output is correct
3 Correct 404 ms 33232 KB Output is correct
4 Correct 406 ms 33228 KB Output is correct
5 Correct 402 ms 33272 KB Output is correct
6 Runtime error 448 ms 67448 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -