| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 259092 | 2020-08-07T07:19:44 Z | ChrisT | 운세 보기 2 (JOI14_fortune_telling2) | C++17 | 415 ms | 33496 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MN = 2e5+2;
struct three {
int first,second,rot;
} cards[MN];
map<int,int> cmp;
pii queries[MN];
int bit[MN];
int sparse[18][MN];
void update (int n, int v) {
for (++n;n<MN;n+=n&-n)
bit[n] += v;
}
int query (int n) {
int ret = 0;
for(++n;n>0;n^=n&-n)
ret += bit[n];
return ret;
}
int mx (int le, int ri) {
auto a = cmp.lower_bound(le), b = cmp.upper_bound(ri);
if (a == cmp.end() || b == cmp.begin()) return -1;
int l = a->second, r = (--b)->second;
if (r < l) return -1;
int log = 31 - __builtin_clz(r-l+1);
return max(sparse[log][l],sparse[log][r-(1<<log)+1]);
}
int main () {
int n,k; ll ans = 0;
scanf ("%d %d",&n,&k);
for (int i = 0; i < n; i++) {
scanf ("%d %d",&cards[i].first,&cards[i].second);
if (cards[i].first > cards[i].second) swap(cards[i].first,cards[i].second), cards[i].rot = 0;
else cards[i].rot = 1;
}
sort(cards,cards+n,[](three a, three b) {return a.second > b.second;});
for (int i = 0; i < k; i++) {
scanf ("%d",&queries[i].first);
queries[i].second = i;
}
sort(queries,queries+k,greater<pii>());
for (int i = k-1; i >= 0; i--) {
if (!cmp[queries[i].first]) cmp[queries[i].first] = k-1-i;
int c = cmp[queries[i].first];
sparse[0][c] = max(sparse[0][c],queries[i].second);
}
for (int len = 1; len < 18; len++) {
for (int i = 0; i < k - (1 << len) + 1; i++) {
sparse[len][i] = max(sparse[len-1][i],sparse[len-1][i+(1<<(len-1))]);
}
}
int ind = 0;
for (int i = 0; i < n; i++) {
three cur = cards[i];
while (ind < k && queries[ind].first >= cur.second) update(queries[ind++].second,1);
int lst = cur.first == cur.second ? -1 : mx(cur.first,cur.second-1);
int rotations = query(k) - query(lst);
if (lst != -1) cur.rot = 0;
ans += (cur.rot + rotations)&1 ? cur.first : cur.second;
}
printf ("%lld\n",ans);
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 512 KB | Output is correct |
| 2 | Correct | 1 ms | 512 KB | Output is correct |
| 3 | Correct | 2 ms | 512 KB | Output is correct |
| 4 | Correct | 2 ms | 512 KB | Output is correct |
| 5 | Correct | 2 ms | 512 KB | Output is correct |
| 6 | Correct | 2 ms | 512 KB | Output is correct |
| 7 | Correct | 2 ms | 512 KB | Output is correct |
| 8 | Correct | 2 ms | 512 KB | Output is correct |
| 9 | Correct | 1 ms | 512 KB | Output is correct |
| 10 | Correct | 1 ms | 512 KB | Output is correct |
| 11 | Correct | 1 ms | 512 KB | Output is correct |
| 12 | Correct | 2 ms | 512 KB | Output is correct |
| 13 | Correct | 1 ms | 512 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 512 KB | Output is correct |
| 2 | Correct | 1 ms | 512 KB | Output is correct |
| 3 | Correct | 2 ms | 512 KB | Output is correct |
| 4 | Correct | 2 ms | 512 KB | Output is correct |
| 5 | Correct | 2 ms | 512 KB | Output is correct |
| 6 | Correct | 2 ms | 512 KB | Output is correct |
| 7 | Correct | 2 ms | 512 KB | Output is correct |
| 8 | Correct | 2 ms | 512 KB | Output is correct |
| 9 | Correct | 1 ms | 512 KB | Output is correct |
| 10 | Correct | 1 ms | 512 KB | Output is correct |
| 11 | Correct | 1 ms | 512 KB | Output is correct |
| 12 | Correct | 2 ms | 512 KB | Output is correct |
| 13 | Correct | 1 ms | 512 KB | Output is correct |
| 14 | Correct | 14 ms | 1980 KB | Output is correct |
| 15 | Correct | 35 ms | 3448 KB | Output is correct |
| 16 | Correct | 44 ms | 5112 KB | Output is correct |
| 17 | Correct | 64 ms | 6648 KB | Output is correct |
| 18 | Correct | 61 ms | 6648 KB | Output is correct |
| 19 | Correct | 60 ms | 6648 KB | Output is correct |
| 20 | Correct | 58 ms | 6652 KB | Output is correct |
| 21 | Correct | 57 ms | 6776 KB | Output is correct |
| 22 | Correct | 41 ms | 5752 KB | Output is correct |
| 23 | Correct | 43 ms | 5624 KB | Output is correct |
| 24 | Correct | 42 ms | 5496 KB | Output is correct |
| 25 | Correct | 43 ms | 5880 KB | Output is correct |
| 26 | Correct | 45 ms | 6520 KB | Output is correct |
| 27 | Correct | 52 ms | 6648 KB | Output is correct |
| 28 | Correct | 51 ms | 6648 KB | Output is correct |
| 29 | Correct | 56 ms | 6732 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 512 KB | Output is correct |
| 2 | Correct | 1 ms | 512 KB | Output is correct |
| 3 | Correct | 2 ms | 512 KB | Output is correct |
| 4 | Correct | 2 ms | 512 KB | Output is correct |
| 5 | Correct | 2 ms | 512 KB | Output is correct |
| 6 | Correct | 2 ms | 512 KB | Output is correct |
| 7 | Correct | 2 ms | 512 KB | Output is correct |
| 8 | Correct | 2 ms | 512 KB | Output is correct |
| 9 | Correct | 1 ms | 512 KB | Output is correct |
| 10 | Correct | 1 ms | 512 KB | Output is correct |
| 11 | Correct | 1 ms | 512 KB | Output is correct |
| 12 | Correct | 2 ms | 512 KB | Output is correct |
| 13 | Correct | 1 ms | 512 KB | Output is correct |
| 14 | Correct | 14 ms | 1980 KB | Output is correct |
| 15 | Correct | 35 ms | 3448 KB | Output is correct |
| 16 | Correct | 44 ms | 5112 KB | Output is correct |
| 17 | Correct | 64 ms | 6648 KB | Output is correct |
| 18 | Correct | 61 ms | 6648 KB | Output is correct |
| 19 | Correct | 60 ms | 6648 KB | Output is correct |
| 20 | Correct | 58 ms | 6652 KB | Output is correct |
| 21 | Correct | 57 ms | 6776 KB | Output is correct |
| 22 | Correct | 41 ms | 5752 KB | Output is correct |
| 23 | Correct | 43 ms | 5624 KB | Output is correct |
| 24 | Correct | 42 ms | 5496 KB | Output is correct |
| 25 | Correct | 43 ms | 5880 KB | Output is correct |
| 26 | Correct | 45 ms | 6520 KB | Output is correct |
| 27 | Correct | 52 ms | 6648 KB | Output is correct |
| 28 | Correct | 51 ms | 6648 KB | Output is correct |
| 29 | Correct | 56 ms | 6732 KB | Output is correct |
| 30 | Correct | 184 ms | 27504 KB | Output is correct |
| 31 | Correct | 237 ms | 28664 KB | Output is correct |
| 32 | Correct | 324 ms | 30200 KB | Output is correct |
| 33 | Correct | 382 ms | 33400 KB | Output is correct |
| 34 | Correct | 156 ms | 27128 KB | Output is correct |
| 35 | Correct | 396 ms | 33400 KB | Output is correct |
| 36 | Correct | 415 ms | 33496 KB | Output is correct |
| 37 | Correct | 395 ms | 33400 KB | Output is correct |
| 38 | Correct | 337 ms | 33476 KB | Output is correct |
| 39 | Correct | 339 ms | 33400 KB | Output is correct |
| 40 | Correct | 311 ms | 33144 KB | Output is correct |
| 41 | Correct | 306 ms | 33400 KB | Output is correct |
| 42 | Correct | 314 ms | 33272 KB | Output is correct |
| 43 | Correct | 247 ms | 32540 KB | Output is correct |
| 44 | Correct | 242 ms | 32248 KB | Output is correct |
| 45 | Correct | 242 ms | 32504 KB | Output is correct |
| 46 | Correct | 238 ms | 28920 KB | Output is correct |
| 47 | Correct | 231 ms | 28024 KB | Output is correct |
| 48 | Correct | 268 ms | 33400 KB | Output is correct |
| 49 | Correct | 278 ms | 33400 KB | Output is correct |