京都大学プログラミングコンテスト2015

Submission #534903

Source codeソースコード

#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>

using namespace std;
typedef long long li;
typedef long double real;

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)

const li bit_max = 1e5 + 10;
li bit[bit_max + 1];
li sum(int i) {
    li s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, li x) {
    while (i <= bit_max) {
        bit[i] += x;
        i += i & -i;
    }
}

int main() {
    li n;
    cin >> n;
    vector<li> a(n), b(n);
    rep(i, n) {
        cin >> a[i];
    }
    rep(i, n) {
        cin >> b[i];
    }
    priority_queue<pair<li, li>> q;
    rep(i, n) {
        q.emplace(a[i], i);
    }

    li ans = 0;
    priority_queue<int> cands;
    for (li i = n-1; i >= 0; --i) {
        while (not q.empty() && q.top().first >= b[i]) {
            cands.emplace(q.top().second);
            //cerr << "ins " << q.top().second << endl;
            q.pop();
        }
        if (cands.empty()) {
            cout << -1 << endl;
            return 0;
        }
        ans += i - cands.top() + sum(cands.top() + 1);
        add(cands.top() + 1, 1);
        //cerr << "out " << cands.top() << ", ans = " << ans << endl;
        cands.pop();
    }
    cout << ans << endl;
    return 0;
}

Submission

Task問題 G - ケンドー
User nameユーザ名 amylase
Created time投稿日時
Language言語 C++11 (GCC 4.9.2)
Status状態 AC
Score得点 300
Source lengthソースコード長 1405 Byte
File nameファイル名
Exec time実行時間 221 ms
Memory usageメモリ使用量 5524 KB

Test case

Set

Set name Score得点 / Max score Cases
Small 3 / 3 00_small_sample_00.txt,00_small_sample_01.txt,00_small_sample_02.txt,10_small_01.txt,10_small_02.txt,10_small_03.txt,10_small_04.txt,10_small_05.txt,10_small_06.txt,10_small_07.txt,10_small_08.txt,10_small_09.txt,10_small_10.txt
All 297 / 297 00_small_sample_00.txt,00_small_sample_01.txt,00_small_sample_02.txt,10_small_01.txt,10_small_02.txt,10_small_03.txt,10_small_04.txt,10_small_05.txt,10_small_06.txt,10_small_07.txt,10_small_08.txt,10_small_09.txt,10_small_10.txt,20_large_01.txt,20_large_02.txt,20_large_03.txt,20_large_04.txt,20_large_05.txt,20_large_06.txt,20_large_07.txt,20_large_08.txt,20_large_09.txt,20_large_10.txt,30_maxcase_01.txt,31_almost_maxcase_01.txt,31_almost_maxcase_02.txt,31_almost_maxcase_03.txt,31_almost_maxcase_04.txt,31_almost_maxcase_05.txt,40_bad_maxcase_01.txt,40_bad_maxcase_02.txt,40_bad_maxcase_03.txt,40_bad_maxcase_04.txt,40_bad_maxcase_05.txt,41_bad_shufflecase_01.txt,41_bad_shufflecase_02.txt,41_bad_shufflecase_03.txt,41_bad_shufflecase_04.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_small_sample_00.txt AC 28 ms 924 KB
00_small_sample_01.txt AC 27 ms 800 KB
00_small_sample_02.txt AC 27 ms 928 KB
10_small_01.txt AC 26 ms 800 KB
10_small_02.txt AC 28 ms 800 KB
10_small_03.txt AC 28 ms 796 KB
10_small_04.txt AC 26 ms 796 KB
10_small_05.txt AC 28 ms 804 KB
10_small_06.txt AC 28 ms 792 KB
10_small_07.txt AC 27 ms 792 KB
10_small_08.txt AC 28 ms 800 KB
10_small_09.txt AC 26 ms 796 KB
10_small_10.txt AC 27 ms 856 KB
20_large_01.txt AC 202 ms 5264 KB
20_large_02.txt AC 201 ms 5264 KB
20_large_03.txt AC 208 ms 5396 KB
20_large_04.txt AC 214 ms 5516 KB
20_large_05.txt AC 208 ms 5388 KB
20_large_06.txt AC 208 ms 5392 KB
20_large_07.txt AC 197 ms 5136 KB
20_large_08.txt AC 209 ms 5324 KB
20_large_09.txt AC 215 ms 5524 KB
20_large_10.txt AC 202 ms 5200 KB
30_maxcase_01.txt AC 159 ms 4756 KB
31_almost_maxcase_01.txt AC 200 ms 4752 KB
31_almost_maxcase_02.txt AC 194 ms 4624 KB
31_almost_maxcase_03.txt AC 198 ms 4752 KB
31_almost_maxcase_04.txt AC 197 ms 4760 KB
31_almost_maxcase_05.txt AC 209 ms 4760 KB
40_bad_maxcase_01.txt AC 185 ms 4376 KB
40_bad_maxcase_02.txt AC 174 ms 4448 KB
40_bad_maxcase_03.txt AC 221 ms 4816 KB
40_bad_maxcase_04.txt AC 175 ms 4376 KB
40_bad_maxcase_05.txt AC 194 ms 4624 KB
41_bad_shufflecase_01.txt AC 185 ms 4756 KB
41_bad_shufflecase_02.txt AC 194 ms 4624 KB
41_bad_shufflecase_03.txt AC 188 ms 4752 KB
41_bad_shufflecase_04.txt AC 179 ms 4680 KB