Submission #1187264

#TimeUsernameProblemLanguageResultExecution timeMemory
1187264TheSahibPilot (NOI19_pilot)C++20
40 / 100
54 ms56136 KiB
#pragma GCC optimize("O3") #pragma GCC target("avx2") #include <iostream> #include <vector> #include <queue> #include <utility> #include <queue> #include <set> #include <map> #include <cmath> #include <vector> #include <iomanip> #include <algorithm> #include <cstring> #include <array> #include <string> #include <stack> using namespace std; #define ll long long #define all(v) v.begin(), v.end() #define pii pair<int, int> const int MAX = 1e6 + 100, MOD = 1e9 + 7; vector<int> v[MAX]; vector<int> mp[MAX]; int ANS[MAX]; void solve(){ int n, q; cin >> n >> q; int arr[n + 2]; int nxt[n + 2]; int prv[n + 2]; for(int i = 1; i <= n; ++i){ cin >> arr[i]; mp[arr[i]].push_back(i); } int ans = 0; for(int i = 1; i <= n; ++i){ prv[i] = i - 1; nxt[i] = i + 1; } for(int y = 0; y < MAX; ++y){ for(int i:mp[y]){ int j = nxt[i]; int k = prv[i]; nxt[k] = j; prv[j] = k; int d1 = (i - k - 1); int d2 = (j - i - 1); int d3 = (j - k - 1); ans -= d1 * (d1 + 1) / 2; ans -= d2 * (d2 + 1) / 2; ans += d3 * (d3 + 1) / 2; } ANS[y] = ans; } for(int i = 0; i < q; ++i){ int y; cin >> y; cout << ANS[y] << '\n'; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while(t--){ solve(); } }
#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...