Submission #570153

#TimeUsernameProblemLanguageResultExecution timeMemory
570153Joshi503Mountains (NOI20_mountains)C++14
64 / 100
2092 ms7032 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using db = long double; using str = string; using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<db, db>; #define f first #define s second #define tcT template<class T #define tcTU tcT, class U tcT> using V = vector<T>; tcT, size_t SZ > using AR = array<T, SZ>; using vi = V<int>; using vb = V<bool>; using vl = V<ll>; using vd = V<db>; using vs = V<str>; using vpi = V<pi>; using vpl = V<pl>; #define sz(x) int((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) x.rbegin(), x.rend() #define sor(x) sort(all(x)) #define pb push_back #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = ((b)-1); i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define rep(a) F0R(_,a) #define each(a,x) for (auto& a: x) const ll MOD = 1e9 + 7; const ll MX = 1e9; const ll INF = 1e18; const db PI = acos((db)-1); const int ddef[4]{ 1,0,-1,0 }, dataq[4]{ 0,1,0,-1 }; mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>; void setIO(string name = "") { ios_base::sync_with_stdio(0); cin.tie(0); if (sz(name)) { freopen((name + ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } } void _print(char i) { cerr << i; } void _print(string i) { cerr << i; } void _print(float i) { cerr << i; } void _print(int i) { cerr << i; } void _print(double i) { cerr << i; } void _print() { cerr << "\n"; }; template<typename x, typename y> void _print(pair<x, y>& t) { cerr << "{";_print(t.first);cerr << ", ";_print(t.second);cerr << "},"; } template<typename x> void _print(x& t) { cerr << "{"; for (int i = 0;i < (int)t.size();i++) { _print(t[i]); if (i < (int)t.size() - 1) cerr << ", "; } cerr << "}"; } template<typename x, typename... y> void _print(x a, y... b) { _print(a);if (sizeof...(b)) cerr << ", ";_print(b...); } #define dbg(x...) cerr<<"["<<#x<<"] = [";_print(x);cerr<<"]\n"; int test; const int MXN = 1e5 * 3; ll a[MXN], n, b; vl segments[600]; ll query(ll l, ll r, ll x){ ll res = 0, ls = l / b, rs = r / b; if(ls == rs){ for(ll i = l; i < r + 1; i++) res += (a[i] >= x); return res; } for(ll i = l; i < ls * b + b; i++) res += (a[i] >= x); for(ll i = rs * b; i < r + 1; i++) res += (a[i] >= x); for(ll i = ls + 1; i < rs; i++){ res += b - (ll)((lower_bound(segments[i].begin(), segments[i].end(), x)) - segments[i].begin()); } return res; } void solve() { cin >> n; ll temp = 1; for(ll i = 1; i * i <= n; i++) temp = i; if(temp * temp < n) temp++; b = temp; F0R(i, 600) if(sz(segments[i])) segments[i].clear(); FOR(i, 1, n + 1){ cin >> a[i]; segments[i / b].pb(a[i]); } ll ans = 0; F0R(i, b + 1) sor(segments[i]); FOR(i, 2, n){ ll x = (i - 1 - query(1, i - 1, a[i])) * (n - i - query(i + 1, n, a[i]) ); // cout << x << "\n"; ans += x; } cout << ans << "\n"; } int main() { setIO(""); int T = 1; // cin >> T; for (test = 1; test <= T; test++) solve(); return 0; }

Compilation message (stderr)

Mountains.cpp: In function 'void setIO(std::string)':
Mountains.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mountains.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen((name + ".out").c_str(), "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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...