oj.uz

Submission #583184

# Submission time Handle Problem Language Result Execution time Memory
583184 2022-06-25T03:02:01 Z Joshi503 Mountains (NOI20_mountains) C++14
100 / 100
 830 ms 45900 KB 
#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 = 3e5;
ll a[MXN + 5];

struct ST{
    int n; 
    vl st;
    ST(int n1){
        n = n1;
        st = vl(n * 4 + 5, 0);
    }

    int left(int node) { return 2 * node; }
    int right(int node) { return 2 * node + 1; }
    void calc(int node) { st[node] = st[left(node)] + st[right(node)]; }
    
    void update(ll k, int v, int tr, int tl = 1, int node = 1){
        if(tl == tr){
            st[node] += v;
            return;
        }
        int mid = (tl + tr) / 2;
        if(k >= tl && k <= mid){
            update(k, v, mid, tl, left(node));
        }
        else update(k, v, tr, mid + 1, right(node));
        calc(node);
    }

    ll query(int ql, int qr, int tr, int tl = 1, int node = 1){
        if(tl >= ql && tr <= qr){
            return st[node];
        }
        if(tr < ql || tl > qr){
            return 0LL;
        }
        int mid = (tl + tr) / 2;
        return query(ql, qr, mid, tl, left(node)) + query(ql, qr, tr, mid + 1, right(node));
    }
};

void solve() {
    int n;
    cin >> n;
    F0R(i, n){
        cin >> a[i];
    }
    map<ll, int> m;
    F0R(i, n){
        m[a[i]] = 1;
    }
    int idx = 1;
    each(x, m){
        m[x.f] = idx++;
    }
    ST st1(n), st2(n);
    F0R(i, n){
        a[i] = m[a[i]];
        st1.update(a[i], 1, n);
    }
    ll ans = 0;
    F0R(i, n){
        st1.update(a[i], -1, n);
        ll x = st1.query(1, a[i] - 1, n), y = st2.query(1, a[i] - 1, n);
        ans += x * y; 
        st2.update(a[i], 1, n);
    }
    cout << ans << "\n";
 
}

int main() {
    setIO("");
    int T = 1;
    // cin >> T;
    for (test = 1; test <= T; test++) solve();
    return 0;
}

Compilation message

Mountains.cpp: In function 'void setIO(std::string)':
Mountains.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mountains.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 346 ms 45744 KB Output is correct
3 Correct 351 ms 45720 KB Output is correct
4 Correct 342 ms 45756 KB Output is correct
5 Correct 328 ms 45636 KB Output is correct
6 Correct 340 ms 45792 KB Output is correct
7 Correct 341 ms 45648 KB Output is correct
8 Correct 340 ms 45736 KB Output is correct
9 Correct 293 ms 36684 KB Output is correct
10 Correct 291 ms 36808 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 21460 KB Output is correct
2 Correct 143 ms 21456 KB Output is correct
3 Correct 136 ms 21364 KB Output is correct
4 Correct 137 ms 21392 KB Output is correct
5 Correct 145 ms 21516 KB Output is correct
6 Correct 140 ms 21456 KB Output is correct
7 Correct 132 ms 21460 KB Output is correct
8 Correct 130 ms 21460 KB Output is correct
9 Correct 141 ms 21456 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 21460 KB Output is correct
2 Correct 143 ms 21456 KB Output is correct
3 Correct 136 ms 21364 KB Output is correct
4 Correct 137 ms 21392 KB Output is correct
5 Correct 145 ms 21516 KB Output is correct
6 Correct 140 ms 21456 KB Output is correct
7 Correct 132 ms 21460 KB Output is correct
8 Correct 130 ms 21460 KB Output is correct
9 Correct 141 ms 21456 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 191 ms 21452 KB Output is correct
12 Correct 198 ms 21464 KB Output is correct
13 Correct 210 ms 21468 KB Output is correct
14 Correct 190 ms 21460 KB Output is correct
15 Correct 193 ms 21580 KB Output is correct
16 Correct 191 ms 21524 KB Output is correct
17 Correct 191 ms 21360 KB Output is correct
18 Correct 158 ms 21468 KB Output is correct
19 Correct 149 ms 21480 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 13 ms 1748 KB Output is correct
12 Correct 14 ms 1748 KB Output is correct
13 Correct 15 ms 1756 KB Output is correct
14 Correct 12 ms 1848 KB Output is correct
15 Correct 13 ms 1848 KB Output is correct
16 Correct 12 ms 1768 KB Output is correct
17 Correct 15 ms 1860 KB Output is correct
18 Correct 10 ms 1492 KB Output is correct
19 Correct 7 ms 1108 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 21460 KB Output is correct
2 Correct 143 ms 21456 KB Output is correct
3 Correct 136 ms 21364 KB Output is correct
4 Correct 137 ms 21392 KB Output is correct
5 Correct 145 ms 21516 KB Output is correct
6 Correct 140 ms 21456 KB Output is correct
7 Correct 132 ms 21460 KB Output is correct
8 Correct 130 ms 21460 KB Output is correct
9 Correct 141 ms 21456 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 191 ms 21452 KB Output is correct
12 Correct 198 ms 21464 KB Output is correct
13 Correct 210 ms 21468 KB Output is correct
14 Correct 190 ms 21460 KB Output is correct
15 Correct 193 ms 21580 KB Output is correct
16 Correct 191 ms 21524 KB Output is correct
17 Correct 191 ms 21360 KB Output is correct
18 Correct 158 ms 21468 KB Output is correct
19 Correct 149 ms 21480 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 522 ms 27508 KB Output is correct
22 Correct 487 ms 27396 KB Output is correct
23 Correct 468 ms 27412 KB Output is correct
24 Correct 464 ms 27488 KB Output is correct
25 Correct 499 ms 27328 KB Output is correct
26 Correct 502 ms 27380 KB Output is correct
27 Correct 454 ms 27416 KB Output is correct
28 Correct 229 ms 27396 KB Output is correct
29 Correct 235 ms 27400 KB Output is correct
30 Correct 0 ms 212 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 346 ms 45744 KB Output is correct
3 Correct 351 ms 45720 KB Output is correct
4 Correct 342 ms 45756 KB Output is correct
5 Correct 328 ms 45636 KB Output is correct
6 Correct 340 ms 45792 KB Output is correct
7 Correct 341 ms 45648 KB Output is correct
8 Correct 340 ms 45736 KB Output is correct
9 Correct 293 ms 36684 KB Output is correct
10 Correct 291 ms 36808 KB Output is correct
11 Correct 141 ms 21460 KB Output is correct
12 Correct 143 ms 21456 KB Output is correct
13 Correct 136 ms 21364 KB Output is correct
14 Correct 137 ms 21392 KB Output is correct
15 Correct 145 ms 21516 KB Output is correct
16 Correct 140 ms 21456 KB Output is correct
17 Correct 132 ms 21460 KB Output is correct
18 Correct 130 ms 21460 KB Output is correct
19 Correct 141 ms 21456 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 191 ms 21452 KB Output is correct
22 Correct 198 ms 21464 KB Output is correct
23 Correct 210 ms 21468 KB Output is correct
24 Correct 190 ms 21460 KB Output is correct
25 Correct 193 ms 21580 KB Output is correct
26 Correct 191 ms 21524 KB Output is correct
27 Correct 191 ms 21360 KB Output is correct
28 Correct 158 ms 21468 KB Output is correct
29 Correct 149 ms 21480 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 13 ms 1748 KB Output is correct
42 Correct 14 ms 1748 KB Output is correct
43 Correct 15 ms 1756 KB Output is correct
44 Correct 12 ms 1848 KB Output is correct
45 Correct 13 ms 1848 KB Output is correct
46 Correct 12 ms 1768 KB Output is correct
47 Correct 15 ms 1860 KB Output is correct
48 Correct 10 ms 1492 KB Output is correct
49 Correct 7 ms 1108 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Correct 522 ms 27508 KB Output is correct
52 Correct 487 ms 27396 KB Output is correct
53 Correct 468 ms 27412 KB Output is correct
54 Correct 464 ms 27488 KB Output is correct
55 Correct 499 ms 27328 KB Output is correct
56 Correct 502 ms 27380 KB Output is correct
57 Correct 454 ms 27416 KB Output is correct
58 Correct 229 ms 27396 KB Output is correct
59 Correct 235 ms 27400 KB Output is correct
60 Correct 0 ms 212 KB Output is correct
61 Correct 830 ms 45796 KB Output is correct
62 Correct 789 ms 45900 KB Output is correct
63 Correct 789 ms 45852 KB Output is correct
64 Correct 738 ms 45792 KB Output is correct
65 Correct 761 ms 45796 KB Output is correct
66 Correct 797 ms 45792 KB Output is correct
67 Correct 814 ms 45792 KB Output is correct
68 Correct 557 ms 36684 KB Output is correct
69 Correct 533 ms 31516 KB Output is correct
70 Correct 1 ms 340 KB Output is correct