| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 594539 | Do_you_copy | Happiness (Balkan15_HAPPINESS) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <ll, ll>;
using pil = pair <ll, ll>;
using pli = pair <ll, ll>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const ll maxN = 1e5 + 1;
const ll inf = 1e12;
ll n;
ll a[maxN];
ll node_cnt = 1;
struct TNode{
TNode *lp, *rp;
ll val;
TNode() : lp(nullptr), rp(nullptr), val(0){}
void update(TNode* id, ll i, ll v, ll l = 1, ll r = inf){
if (i < l || i > r) return;
id->val += v;
if (l == r){
return;
}
id->create_node();
ll mid = (l + r) / 2;
update(id->lp, i, v, l, mid);
update(id->rp, i, v, mid + 1, r);
}
void create_node(){
if (!lp) lp = new TNode();
if (!rp) rp = new TNode();
}
ll get(TNode* id, ll i, ll j, ll l = 1, ll r = inf){
if (r < i || l > j) return 0;
if (i <= l && r <= j) return id->val;
ll mid = (l + r) / 2;
ll ret = 0;
if (id->lp) ret += get(id->lp, i, j, l, mid);
if (id->rp) ret += get(id->rp, i, j, mid + 1, r);
return ret;
}
};
TNode* st;
bool check(){
ll tem = 1, last = st->val;
while (tem < last){
ll t = st->get(st, 1, tem);
if (t < tem) return 0;
tem = t + 1;
}
return 1;
}
bool init(int N, ll M, ll a[]){
n = N;
st = new TNode();
for (ll i = 0; i < n; ++i) st->update(st, a[i], a[i]);
return check();
}
bool is_happy(int t, int K, ll a[]){
for (ll i = 0; i < K; ++i) st->update(st, a[i], a[i] * t);
return check();
}
int main(){
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
}
faster;
ll tt = 1;
//cin >> tt;
while (tt--){
ll nn, mx;
cin >> nn >> mx;
ll aa[nn];
for (ll i = 0; i < nn; ++i) cin >> aa[i];
cout << init(nn, mx, aa) << "\n";
ll qq; cin >> qq;
while (qq--){
ll ttt, cnt;
cin >> ttt >> cnt;
ll bb[cnt];
for (ll i = 0; i < cnt; ++i) cin >> bb[i];
cout << is_happy(ttt, cnt, bb) << "\n";
}
}
}