oj.uz

Submission #401321

# Submission time Handle Problem Language Result Execution time Memory
401321 2021-05-09T20:42:55 Z hgmhc 공장 (KOI13_factory) C++14
20 / 20
 820 ms 17016 KB 
#include <iostream>
#include <tuple>
#include <numeric>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <cassert>
#include <climits>
#include <string>
#define endl '\n'
#define REP(i,a,b) for (int i = a; i <= b; ++i)
#define PER(i,a,b) for (int i = b; i >= a; --i)
#define all(x) x.begin(), x.end()
#define debug cout << "dbg"
#define debugprint(x) cout << endl << #x << " is " << x << endl
using namespace std; void solve(); int main() {
    ios::sync_with_stdio(0); cin.tie(0); solve();}
using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>;

const int N = 524290, M = 1000003;
int n, tree[N<<1], ord[M];

void update(int t, int x, iii node = {1,1,n}) {
    auto [k,l,r] = node;
    if (t < l || r < t) return;
    if (l == r) {tree[k] += x; return;}
    int m = (l+r)>>1;
    update(t,x,{k<<1,l,m}); update(t,x,{(k<<1)|1,m+1,r});
    tree[k] = tree[k<<1]+tree[(k<<1)|1];
} void update(ii range, int x) {
    auto [s,e] = range;
    update(s,x);
    update(e+1,-x);
}

auto query(int t, iii node = {1,1,n}) {
    auto [k,l,r] = node;
    if (t-1 < l || r < 1) return tree[0];
    if (1 <= l && r <= t-1) return tree[k];
    int m = (l+r)>>1;
    return query(t,{k<<1,l,m})+query(t,{(k<<1)|1,m+1,r});
}

void solve() {
    cin >> n;
    int id[n];
    for (auto& s : id) cin >> s;
    REP(i,1,n) {
        int x; cin >> x;
        ord[x] = i;
    }
    REP(i,1,n) update({i,n},1);
//    REP(i,1,n) cout << query(i) << endl;
    ll ans = 0;
    for (auto i : id) {
        ans += query(ord[i]);
        update({ord[i],n},-1);
    }
    cout << ans;
}

Compilation message

factory.cpp: In function 'void update(int, int, iii)':
factory.cpp:26:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     auto [k,l,r] = node;
      |          ^
factory.cpp: In function 'void update(ii, int)':
factory.cpp:33:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     auto [s,e] = range;
      |          ^
factory.cpp: In function 'auto query(int, iii)':
factory.cpp:39:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     auto [k,l,r] = node;
      |          ^

Subtask #1
2.2 / 2.2

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 7 ms 4300 KB Output is correct
3 Correct 13 ms 4428 KB Output is correct

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4932 KB Output is correct
2 Correct 66 ms 5628 KB Output is correct
3 Correct 92 ms 6536 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 140 ms 6976 KB Output is correct
2 Correct 230 ms 9060 KB Output is correct
3 Correct 277 ms 9724 KB Output is correct
4 Correct 450 ms 13440 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 660 ms 15276 KB Output is correct
2 Correct 680 ms 17016 KB Output is correct
3 Correct 690 ms 17016 KB Output is correct
4 Correct 809 ms 17016 KB Output is correct
5 Correct 820 ms 16920 KB Output is correct
6 Correct 784 ms 16928 KB Output is correct