Submission #312833

#TimeUsernameProblemLanguageResultExecution timeMemory
312833daringtriflesMountains (NOI20_mountains)C++17
36 / 100
2085 ms7928 KiB
//control+option+n to run! #include <bits/stdc++.h> using namespace std; #define pb push_back #define ll long long #define pll pair<ll, ll> #define FOR(i, a, b) for (signed long long i = (signed long long)(a); i < (signed long long)(b); i++) #define NEGFOR(i, a, b) for (ll i = (a); i > (b); i--) #define vll vector<long long> #define sll set<long long> #define ld long double #define inf 1000000000000000000 #define mll multiset<long long> #define vpll vector<pll> #define nn << "\n" #define ss << " " #define F(i, b) for (ll i = 0; i < b; i++) //10^8 operations per second //greatest int is 2,147,483,647 //greates long long is 9.22337204e18 //ALL FUNCTIONS SHOULD BE LL!!!! ll power(ll x, ll n, ll m) { assert(n >= 0); x %= m; //note: m*m must be less than 2^63 to avoid ll overflow ll res = 1; while (n > 0) { if (n % 2 == 1) //if n is odd res = res * x % m; x = x * x % m; n /= 2; //divide by two } return res; } ll log(ll base, ll number) { int x = base; int count = 1; while (base < number) { base *= x; count++; } return count; } //#define oi int main() { #ifdef oi ifstream cin("file.in"); ofstream cout("file.out"); #endif #ifndef oi ios_base::sync_with_stdio(false); cin.tie(NULL); #endif clock_t tStart = clock(); ll n; cin >> n; vll v(n); FOR(i, 0, n) cin >> v[i]; vll before(n, 0), after(n, 0), x; ll ans = 0; x.pb(v[0]); FOR(i, 1, n) { before[i] = lower_bound(x.begin(), x.end(), v[i]) - x.begin(); x.pb(v[i]); sort(x.begin(), x.end()); } x={}; x.pb(v[n-1]); FOR(i, 1, n) { after[i] = lower_bound(x.begin(), x.end(), v[n-i-1])-x.begin(); x.pb(v[n-i-1]); sort(x.begin(), x.end()); } FOR(i,0,n){ ans+=before[i]*after[n-1-i]; } cout<<ans; cerr nn << (double)(clock() - tStart) / CLOCKS_PER_SEC; }
#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...