Submission #401321

#	Time	Username	Problem	Language	Result	Execution time	Memory
401321		hgmhc	공장 (KOI13_factory)	C++14	20 / 20	820 ms	17016 KiB

factory

#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 (stderr)

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
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 4.8 / 4.8
• Subtask 5: 5.8 / 5.8