Submission #320742

#TimeUsernameProblemLanguageResultExecution timeMemory
320742arujbansalPilot (NOI19_pilot)C++17
100 / 100
738 ms75552 KiB
#include <bits/stdc++.h> #define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) #define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout) #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int) (x).size() #define lc(i) 2*i #define rc(i) 2*i+1 #define int long long using namespace std; using ll = long long; using ii = pair<int, int>; using vii = vector<ii>; using vi = vector<int>; using vvi = vector<vi>; using vb = vector<bool>; using vvb = vector<vb>; const int N = 1e5 + 5, MOD = 1e9 + 7, INF = 1e9 + 5; struct UFDS { int n, validFlights; vector<int> par, s; vector<bool> active; void init(int x) { n = x; validFlights = 0; par.resize(n); iota(all(par), 0); s.assign(n, 1); active.assign(n, false); } int get(int x) { if (par[x] == x) return x; return par[x] = get(par[x]); } bool unite(int x, int y) { x = get(x); y = get(y); if (!active[x]) { active[x] = true; validFlights += s[x]; } if (!active[y] || x == y) return false; if (s[x] < s[y]) swap(x, y); validFlights -= flights(s[x]) + flights(s[y]); s[x] += s[y]; par[y] = x; validFlights += flights(s[x]); return true; } int getSz(int x) { x = get(x); return s[x]; } int flights(int x) { return x * (x + 1) / 2; } }; signed main() { FAST_IO; #ifdef arujbansal_local setIO("input.txt", "output.txt"); #endif int n, q; cin >> n >> q; vii h(n); for (int i = 0; i < n; i++) { cin >> h[i].first; h[i].second = i; } sort(all(h)); vii queries(q); for (int i = 0; i < q; i++) { cin >> queries[i].first; queries[i].second = i; } sort(all(queries)); UFDS mountains; mountains.init(n); int ans[q]; int j = 0; for (const auto &[plane, idx] : queries) { while (j < n && h[j].first <= plane) { int cur = h[j].second; int prev = cur - 1; int next = cur + 1; if (prev >= 0) mountains.unite(cur, prev); if (next < n) mountains.unite(cur, next); j++; } ans[idx] = mountains.validFlights; } for (const auto &x : ans) cout << x << "\n"; }
#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...
#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...