답안 #76469 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76469	2018-09-13T14:40:07 Z	win11905	운세 보기 2 (JOI14_fortune_telling2)	C++11	35 / 100	3000 ms	94424 KB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define long long long
#define pii pair<int, int>
#define x first
#define y second

const int N = 2e5+5;

int n, k;

long ans;
vector<int> t[N<<1];
vector<pii> que;

int f(int m, int v) {
    int sum = 0;
    auto get = [&](int z) {
        int x = lower_bound(all(t[z]), v) - t[z].begin() - 1;
        sum += t[z].size() - x - 1;
    };
    for(int l = m + k, r = k + k; l < r; l >>= 1, r >>= 1) {
        if(l & 1) get(l++);
        if(r & 1) get(--r);
    }
    return sum;
}

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0, a, b; i < n; ++i) {
        scanf("%d %d", &a, &b);
        que.emplace_back(a, b);
    }
    k++, t[k].emplace_back(0);
    for(int i = 1, ret; i < k; ++i) {
        scanf("%d", &ret);
        t[i+k].emplace_back(ret);
    }
    for(int i = k-1; i; --i) merge(all(t[i<<1]), all(t[i<<1|1]), back_inserter(t[i]));
    for(auto x : que) {
        int a, b; tie(a, b) = x;
        int l = 0, r = k;
        while(l < r) {
            int m = (l + r + 1) >> 1;
            if(f(m, a) != f(m, b)) l = m;
            else r = m-1;
        }
        long pa = ans;
        if(l == 0) ans += f(0, a) & 1 ? b : a;
        else ans += f(l, max(a, b)) & 1 ? min(a, b) : max(a, b);
    }
    printf("%lld\n", ans);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:51:14: warning: unused variable 'pa' [-Wunused-variable]
         long pa = ans;
              ^~
fortune_telling2.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ret);
         ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9848 KB	Output is correct
2	Correct	13 ms	9940 KB	Output is correct
3	Correct	12 ms	9948 KB	Output is correct
4	Correct	26 ms	10156 KB	Output is correct
5	Correct	14 ms	10156 KB	Output is correct
6	Correct	13 ms	10156 KB	Output is correct
7	Correct	15 ms	10200 KB	Output is correct
8	Correct	16 ms	10272 KB	Output is correct
9	Correct	11 ms	10304 KB	Output is correct
10	Correct	13 ms	10332 KB	Output is correct
11	Correct	14 ms	10376 KB	Output is correct
12	Correct	16 ms	10376 KB	Output is correct
13	Correct	18 ms	10404 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9848 KB	Output is correct
2	Correct	13 ms	9940 KB	Output is correct
3	Correct	12 ms	9948 KB	Output is correct
4	Correct	26 ms	10156 KB	Output is correct
5	Correct	14 ms	10156 KB	Output is correct
6	Correct	13 ms	10156 KB	Output is correct
7	Correct	15 ms	10200 KB	Output is correct
8	Correct	16 ms	10272 KB	Output is correct
9	Correct	11 ms	10304 KB	Output is correct
10	Correct	13 ms	10332 KB	Output is correct
11	Correct	14 ms	10376 KB	Output is correct
12	Correct	16 ms	10376 KB	Output is correct
13	Correct	18 ms	10404 KB	Output is correct
14	Correct	77 ms	11760 KB	Output is correct
15	Correct	166 ms	13672 KB	Output is correct
16	Correct	269 ms	15660 KB	Output is correct
17	Correct	373 ms	18216 KB	Output is correct
18	Correct	387 ms	19364 KB	Output is correct
19	Correct	360 ms	20524 KB	Output is correct
20	Correct	392 ms	21944 KB	Output is correct
21	Correct	289 ms	22864 KB	Output is correct
22	Correct	139 ms	23620 KB	Output is correct
23	Correct	136 ms	24304 KB	Output is correct
24	Correct	145 ms	24996 KB	Output is correct
25	Correct	138 ms	25676 KB	Output is correct
26	Correct	443 ms	26648 KB	Output is correct
27	Correct	642 ms	27820 KB	Output is correct
28	Correct	413 ms	29004 KB	Output is correct
29	Correct	668 ms	30156 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9848 KB	Output is correct
2	Correct	13 ms	9940 KB	Output is correct
3	Correct	12 ms	9948 KB	Output is correct
4	Correct	26 ms	10156 KB	Output is correct
5	Correct	14 ms	10156 KB	Output is correct
6	Correct	13 ms	10156 KB	Output is correct
7	Correct	15 ms	10200 KB	Output is correct
8	Correct	16 ms	10272 KB	Output is correct
9	Correct	11 ms	10304 KB	Output is correct
10	Correct	13 ms	10332 KB	Output is correct
11	Correct	14 ms	10376 KB	Output is correct
12	Correct	16 ms	10376 KB	Output is correct
13	Correct	18 ms	10404 KB	Output is correct
14	Correct	77 ms	11760 KB	Output is correct
15	Correct	166 ms	13672 KB	Output is correct
16	Correct	269 ms	15660 KB	Output is correct
17	Correct	373 ms	18216 KB	Output is correct
18	Correct	387 ms	19364 KB	Output is correct
19	Correct	360 ms	20524 KB	Output is correct
20	Correct	392 ms	21944 KB	Output is correct
21	Correct	289 ms	22864 KB	Output is correct
22	Correct	139 ms	23620 KB	Output is correct
23	Correct	136 ms	24304 KB	Output is correct
24	Correct	145 ms	24996 KB	Output is correct
25	Correct	138 ms	25676 KB	Output is correct
26	Correct	443 ms	26648 KB	Output is correct
27	Correct	642 ms	27820 KB	Output is correct
28	Correct	413 ms	29004 KB	Output is correct
29	Correct	668 ms	30156 KB	Output is correct
30	Correct	288 ms	52180 KB	Output is correct
31	Correct	838 ms	55444 KB	Output is correct
32	Correct	1526 ms	59892 KB	Output is correct
33	Correct	2916 ms	66436 KB	Output is correct
34	Correct	204 ms	66436 KB	Output is correct
35	Correct	2950 ms	74164 KB	Output is correct
36	Correct	2830 ms	79960 KB	Output is correct
37	Correct	2843 ms	85756 KB	Output is correct
38	Correct	2802 ms	91556 KB	Output is correct
39	Correct	2840 ms	94288 KB	Output is correct
40	Correct	2144 ms	94288 KB	Output is correct
41	Correct	2868 ms	94288 KB	Output is correct
42	Correct	2811 ms	94328 KB	Output is correct
43	Correct	874 ms	94328 KB	Output is correct
44	Correct	912 ms	94328 KB	Output is correct
45	Correct	937 ms	94328 KB	Output is correct
46	Correct	956 ms	94328 KB	Output is correct
47	Correct	1227 ms	94328 KB	Output is correct
48	Execution timed out	3034 ms	94424 KB	Time limit exceeded
49	Halted	0 ms	0 KB	-

답안 #76469

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
0 / 65.0