Submission #535000

#TimeUsernameProblemLanguageResultExecution timeMemory
535000Killer2501Self Study (JOI22_ho_t2)C++14
100 / 100
253 ms17808 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define pb push_back #define pll pair<ll, int> #define pii pair<int, int> #define fi first #define se second using namespace std; const int N = 3e5+5; const int M = 8; const int mod = 998244353; const int base = 350; const ll inf = 1e18+7; int m, n, k, t, c[N], d[N], dp[N][3], L, R, in[N], out[N], pos[N]; ll ans, tong, b[N], a[N]; vector<int> adj[N]; string s; int r, sz, ntime; struct BIT { int n; vector<int> fe; BIT(){} void init(int _n) { n = _n; fe.assign(n+1, 0); } void add(int id, int x) { ++id; for(; id <= n; id += id & -id)fe[id] += x; } int get(int id) { ++id; id = min(id, n); if(id <= 0)return 0; int total = 0; for(; id; id -= id & -id)total += fe[id]; return total; } int get(int l, int r) { return get(r) - get(l-1); } }bit[3]; void dfs(int u, int p = 0) { int mx = 0; d[u] = 1; for(int v: adj[u]) { if(v == p || b[v])continue; dfs(v, u); d[u] += d[v]; mx = max(d[v], mx); } mx = max(mx, sz-d[u]); if(mx*2 <= sz)r = u; } void cal(int u, int p = 0) { if(L <= c[u] && c[u] <= R)++ans; in[u] = ++ntime; pos[ntime] = u; for(int v: adj[u]) { if(v == p || b[v])continue; c[v] = c[u]; if(p && a[u] > a[p] && a[u] > a[v])++c[v]; cal(v, u); } out[u] = ntime; } void decom(int u) { //cout << u << endl; int all = sz; b[u] = 1; ntime = 0; c[u] = 0; cal(u); //cout << u << '\n'; //for(int j = in[u]; j <= out[u]; j ++)cout << pos[j] <<" "<< c[pos[j]] << '\n'; for(int v: adj[u]) { if(b[v])continue; if(a[v] < a[u]) { for(int j = in[v]; j <= out[v]; j ++) { int x = pos[j]; ans += bit[0].get(L-c[x], R-c[x]); ans += bit[1].get(L-c[x]-1, R-c[x]-1); } for(int j = in[v]; j <= out[v]; j ++) { int x = pos[j]; bit[1].add(c[x], 1); } } else { for(int j = in[v]; j <= out[v]; j ++) { int x = pos[j]; ans += bit[0].get(L-c[x], R-c[x]); ans += bit[1].get(L-c[x], R-c[x]); } for(int j = in[v]; j <= out[v]; j ++) { int x = pos[j]; bit[0].add(c[x], 1); } } } for(int v: adj[u]) { if(b[v])continue; if(a[v] < a[u]) { for(int j = in[v]; j <= out[v]; j ++) { int x = pos[j]; bit[1].add(c[x], -1); } } else { for(int j = in[v]; j <= out[v]; j ++) { int x = pos[j]; bit[0].add(c[x], -1); } } } for(int v: adj[u]) { if(b[v])continue; sz = d[v] > d[u] ? all-d[u] : d[v]; dfs(v); decom(r); } } void sol() { cin >> n >> m; for(int i = 1; i <= n; i ++)cin >> a[i]; for(int i = 1; i <= n; i ++)cin >> b[i]; ll l = 1, r = inf, mid; while(l <= r) { mid = (l+r)>>1; ll need = 0, have = 0; for(int i = 1; i <= n; i ++) { if(a[i] >= b[i]) { if(a[i]*m >= mid)have += m-(mid+a[i]-1)/a[i]; else need += (mid-a[i]*m+b[i]-1)/b[i]; } else { if(b[i]*m >= mid)have += m-(mid+b[i]-1)/b[i]; else need += (mid-b[i]*m+b[i]-1)/b[i]; } if(need > 1ll*n*m)break; } if(have >= need)l = mid+1; else r = mid-1; } cout << r; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); #define task "test" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; //cin >> test; while(test -- > 0)sol(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.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(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.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(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...