oj.uz

Submission #169487

# Submission time Handle Problem Language Result Execution time Memory
169487 2019-12-20T16:26:38 Z tcm Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 1236 ms 55844 KB 
#include <bits/stdc++.h>
#define fname "FORTELL2"
#define bug(x) cerr << (#x) << " = " << (x) << '\n'
#define ll long long
#define ld long double
#define ull unsigned long long
#define ui unsigned int
#define REP0(i, n) for(int i = 0, _n = (n); i < _n; ++i)
#define REP1(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define REPB0(i, n) for(int i = (n) - 1; i >= 0; --i)
#define REPB1(i, n) for(int i = (n); i > 0; --i)
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORB(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ARR0(a, n) {cerr <<(#a)<< ": ["; REP0(i, n) cerr<< ' ' << a[i] <<','; cerr<<"]\n";}
#define ARR1(a, n) {cerr <<(#a)<< ": ["; REP1(i, n) cerr<< ' ' << a[i] <<','; cerr<<"]\n";}
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ins insert
#define ers erase
#define LB lower_bound
#define UB upper_bound
#define X first
#define Y second

using namespace std;
template<typename T, typename V>
inline void bugp(const pair<T, V> &x) {cerr << '{' << x.X << ", " << x.Y << "}\n";}
template<typename T, typename U, typename V>
inline void bugpp(const pair<T, pair<U, V> > &x) {cerr << '{' << x.X << ", {" << x.Y.X << ", " << x.Y.Y << "}}\n";}
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef pair<float, float> ff;
typedef pair<int, ii> iii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef pair<ll, ii> lii;
const int N = 200002, K = 200002;
int n, k, sz, H[N+N+K], arr[N+N+K], Max[N+N+K << 2], ans[N], ind[K], fen[N+N+K];
ii coin[N];
struct Query {
    int C, id;
    bool operator <(const Query &qq) const {return C > qq.C;}
} Q[K];
struct Que {
    int val, L, R, id;
    bool operator <(const Que &qq) const {return val > qq.val;}
} data[N];

inline bool cmp(const Query &q1, const Query &q2) {return q1.id < q2.id;}
void compress()
{
    set<int> s;
    REP1(i, n) {
        s.ins(coin[i].X);
        s.ins(coin[i].Y);
    }
    REP1(i, k) s.ins(Q[i].C);
    vector<int> tmp(s.begin(), s.end());
    int temp;
    REP1(i, n) {
        temp = LB(tmp.begin(), tmp.end(), coin[i].X) - tmp.begin() + 1;
        H[temp] = coin[i].X;
        coin[i].X = temp;
        temp = LB(tmp.begin(), tmp.end(), coin[i].Y) - tmp.begin() + 1;
        H[temp] = coin[i].Y;
        coin[i].Y = temp;
    }
    REP1(i, k) {
        Q[i].C = LB(tmp.begin(), tmp.end(), Q[i].C) - tmp.begin() + 1;
        arr[Q[i].C] = i;
    }
    sz = tmp.size();
}
void build(int x = 1, int l = 1, int r = sz)
{
    if(l == r) Max[x] = arr[l];
    else {
        int mid = (l + r) >> 1;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
    }
}
int getMax(int u, int v, int x = 1, int l = 1, int r = sz)
{
    if(u > r || v < l) return INT_MIN;
    else if(u <= l && r <= v) return Max[x];
    int mid = (l + r) >> 1;
    return max(getMax(u, v, x << 1, l, mid), getMax(u, v, x << 1 | 1, mid + 1, r));
}
void update(int i) {for(; i <= sz; i += i&-i) ++fen[i];}
int getSum(int u, int v)
{
    int fi = 0, se = 0;
    --u;
    for(; u; u &= u - 1) fi += fen[u];
    for(; v; v &= v - 1) se += fen[v];
    return se - fi;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
    scanf("%d %d", &n, &k);
    REP1(i, n) scanf("%d %d", &coin[i].X, &coin[i].Y);
    REP1(i, k) {
        scanf("%d", &Q[i].C);
        Q[i].id = i;
    }
    compress();
    build();
    int pos, x, y, cnt = 0;
    REP1(i, n) {
        if(coin[i].X == coin[i].Y) ans[i] = H[coin[i].X];
        else {
            x = min(coin[i].X, coin[i].Y);
            y = max(coin[i].X, coin[i].Y);
            pos = getMax(x, y - 1);
            if(pos == k) ans[i] = H[y];
            else if(!pos) data[++cnt] = {coin[i].X, pos + 1, k, i};
            else data[++cnt] = {y, pos + 1, k, i};
        }
    }
    sort(data + 1, data + cnt + 1);
    sort(Q + 1, Q + k + 1);
    REP1(i, k) ind[i] = Q[i].id;
    sort(Q + 1, Q + k + 1, cmp);
    int j = 1, res;
    REP1(i, cnt) {
        while(Q[ind[j]].C >= data[i].val && j <= k) update(ind[j++]);
        res = getSum(data[i].L, data[i].R);
        if(res&1) {
            if(data[i].val == coin[data[i].id].X)
                ans[data[i].id] = H[coin[data[i].id].Y];
            else ans[data[i].id] = H[coin[data[i].id].X];
        }
        else ans[data[i].id] = H[data[i].val];
    }
    ll sum = 0;
    REP1(i, n) sum += ans[i];
    cout << sum;
	return 0;
}

Compilation message

fortune_telling2.cpp:40:44: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 int n, k, sz, H[N+N+K], arr[N+N+K], Max[N+N+K << 2], ans[N], ind[K], fen[N+N+K];
                                         ~~~^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:106: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:107:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     REP1(i, n) scanf("%d %d", &coin[i].X, &coin[i].Y);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &Q[i].C);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 4 ms 632 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 4 ms 632 KB Output is correct
14 Correct 29 ms 3064 KB Output is correct
15 Correct 63 ms 5556 KB Output is correct
16 Correct 104 ms 8280 KB Output is correct
17 Correct 137 ms 10644 KB Output is correct
18 Correct 140 ms 10640 KB Output is correct
19 Correct 142 ms 10640 KB Output is correct
20 Correct 146 ms 10832 KB Output is correct
21 Correct 141 ms 10208 KB Output is correct
22 Correct 94 ms 7788 KB Output is correct
23 Correct 83 ms 6272 KB Output is correct
24 Correct 75 ms 5692 KB Output is correct
25 Correct 93 ms 8068 KB Output is correct
26 Correct 94 ms 8012 KB Output is correct
27 Correct 113 ms 8676 KB Output is correct
28 Correct 100 ms 8624 KB Output is correct
29 Correct 122 ms 9800 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 4 ms 632 KB Output is correct
13 Correct 4 ms 632 KB Output is correct
14 Correct 29 ms 3064 KB Output is correct
15 Correct 63 ms 5556 KB Output is correct
16 Correct 104 ms 8280 KB Output is correct
17 Correct 137 ms 10644 KB Output is correct
18 Correct 140 ms 10640 KB Output is correct
19 Correct 142 ms 10640 KB Output is correct
20 Correct 146 ms 10832 KB Output is correct
21 Correct 141 ms 10208 KB Output is correct
22 Correct 94 ms 7788 KB Output is correct
23 Correct 83 ms 6272 KB Output is correct
24 Correct 75 ms 5692 KB Output is correct
25 Correct 93 ms 8068 KB Output is correct
26 Correct 94 ms 8012 KB Output is correct
27 Correct 113 ms 8676 KB Output is correct
28 Correct 100 ms 8624 KB Output is correct
29 Correct 122 ms 9800 KB Output is correct
30 Correct 341 ms 20092 KB Output is correct
31 Correct 494 ms 28060 KB Output is correct
32 Correct 687 ms 35540 KB Output is correct
33 Correct 1170 ms 54552 KB Output is correct
34 Correct 280 ms 16988 KB Output is correct
35 Correct 1236 ms 55500 KB Output is correct
36 Correct 1118 ms 54488 KB Output is correct
37 Correct 1149 ms 55416 KB Output is correct
38 Correct 1125 ms 55484 KB Output is correct
39 Correct 1109 ms 55744 KB Output is correct
40 Correct 1036 ms 51252 KB Output is correct
41 Correct 1139 ms 55844 KB Output is correct
42 Correct 1079 ms 55824 KB Output is correct
43 Correct 636 ms 49408 KB Output is correct
44 Correct 656 ms 49480 KB Output is correct
45 Correct 647 ms 49952 KB Output is correct
46 Correct 555 ms 31992 KB Output is correct
47 Correct 473 ms 25948 KB Output is correct
48 Correct 758 ms 40540 KB Output is correct
49 Correct 779 ms 40628 KB Output is correct