| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 870030 |
2023-11-06T16:47:52 Z |
thienhx |
Meteors (POI11_met) |
C++17 |
|
647 ms |
31324 KB |
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using str = string;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
//--------------------
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)((x).size())
#define mem(f,x) memset(f , x , sizeof(f))
#define MASK(x) (1ll << (x))
#define cntbit(x) __builtin_popcountll(x)
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
//--------------------
template<class T>inline bool maximize(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool minimize(T&a,const T&b){return a>b?a=b,1:0;}
#define PROBLEM "test"
const int MOD = 1e9 + 7; // 998244353;
const ll INF = 1e18;
const ld PI = acos(-1.0);
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // U R D L
//-----------------[PROBLEM SOLUTION]-----------------//
const int maxn = 3e5 + 15;
ll lim[maxn], amt[maxn], res[maxn], ind = 0;
pll range[maxn];
vector<ll> pos[maxn];
struct BIT1D {
ll n;
vector<ll> bit;
BIT1D(ll _n) : n(_n) {
bit.assign(n + 1, 0);
}
void reset() {
for (int i = 0; i <= n; i++)
bit[i] = 0;
}
ll Query(ll p) {
ll res = 0;
for (; p > 0; p -= (p & (-p)))
res += bit[p];
return res;
}
void Update(ll p, ll x) {
for (; p <= n; p += (p & (-p)))
bit[p] += x;
}
void Update2(ll l, ll r, ll x) {
Update(l, x);
Update(r + 1, -x);
}
};
struct State {
ll L, R;
vector<ll> st;
State() { }
};
void solve() {
ll n, m, k;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
ll x;
cin >> x;
pos[x].pb(i);
}
for (int i = 1; i <= n; i++)
cin >> lim[i];
cin >> k;
for (int i = 1; i <= k; i++)
cin >> range[i].F >> range[i].S >> amt[i];
State tmp;
tmp.L = 1, tmp.R = k + 1;
for (int i = 1; i <= n; i++) tmp.st.pb(i);
BIT1D bit(m);
queue<State> q;
q.push(tmp);
while(q.size()) {
State cur = q.front(); q.pop();
if(cur.L < cur.R) {
ll mid = (cur.L + cur.R) / 2;
if(ind > mid) ind = 0, bit.reset();
while(ind < mid) {
ind++;
if(range[ind].F <= range[ind].S) bit.Update2(range[ind].F, range[ind].S, amt[ind]);
else bit.Update2(range[ind].F, m, amt[ind]), bit.Update2(1, range[ind].S, amt[ind]);
}
State stL, stR;
stL.L = cur.L, stL.R = mid;
stR.L = mid + 1, stR.R = cur.R;
for (int v : cur.st) {
ll sum = 0;
for (int p : pos[v])
sum += bit.Query(p);
if(sum >= lim[v]) stL.st.pb(v);
else stR.st.pb(v);
}
if(stL.st.size()) q.push(stL);
if(stR.st.size()) q.push(stR);
}
else
for (int v : cur.st) res[v] = cur.R;
}
for (int i = 1; i <= n; i++) {
if (res[i] <= k) cout << res[i] << '\n';
else cout << "NIE" << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(PROBLEM".inp", "r")){
freopen(PROBLEM".inp", "r", stdin);
freopen(PROBLEM".out", "w", stdout);
}
constexpr bool MULTI_TEST = 0;
int t = 1;
if(MULTI_TEST) cin >> t;
while(t--)
solve();
}
Compilation message
met.cpp: In function 'int main()':
met.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
145 | freopen(PROBLEM".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | freopen(PROBLEM".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
4 ms |
12976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
14144 KB |
Output is correct |
| 2 |
Correct |
75 ms |
18408 KB |
Output is correct |
| 3 |
Correct |
66 ms |
16104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
14592 KB |
Output is correct |
| 2 |
Correct |
67 ms |
15876 KB |
Output is correct |
| 3 |
Correct |
74 ms |
18588 KB |
Output is correct |
| 4 |
Correct |
22 ms |
15212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
14416 KB |
Output is correct |
| 2 |
Correct |
64 ms |
18820 KB |
Output is correct |
| 3 |
Correct |
18 ms |
13400 KB |
Output is correct |
| 4 |
Correct |
67 ms |
16516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
13784 KB |
Output is correct |
| 2 |
Correct |
71 ms |
15940 KB |
Output is correct |
| 3 |
Correct |
48 ms |
15192 KB |
Output is correct |
| 4 |
Correct |
80 ms |
19256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
547 ms |
31324 KB |
Output is correct |
| 2 |
Incorrect |
600 ms |
29256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
644 ms |
30092 KB |
Output is correct |
| 2 |
Incorrect |
647 ms |
27600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
