oj.uz

Submission #591884

# Submission time Handle Problem Language Result Execution time Memory
591884 2022-07-08T06:05:32 Z Do_you_copy Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 48 ms 8872 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;

int n, k;

struct TCard{
    int high, low, idx;
};

struct TQ{
    int val, idx1, idx2;
};

TQ flip[maxN];
TCard b[maxN];
int bit[maxN];
int bit2[maxN];
vector <pii> t;
pii a[maxN];
int c[maxN];
int cnt[maxN];
int cnt1[maxN];

void update(int xx, int val){
    int x = upper_bound(t.begin(), t.end(), xx,[](const auto &i, const auto &j){
        return i < j.first;
    }) - t.begin();
    for (; x; x -= x & -x){
        bit[x] = max(bit[x], val);
    }
}

void update2(int xx, int val){
    int x = upper_bound(t.begin(), t.end(), xx,[](const auto &i, const auto &j){
        return i < j.first;
    }) - t.begin();
    x = t.size() - x + 1;
    for (; x <= t.size(); x += x & -x){
        bit2[x] += val;
    }
}

int get(int xx){
    int x = lower_bound(t.begin(), t.end(), xx,[](const auto &i, const auto &j){
        return i.fi < j;
    }) - t.begin() + 1;
    ll res = 0;
    for (; x <= t.size(); x += x & -x){
        res = max(res, bit[x]);
    }
    return res;
}

int get2(int xx){
    int x = lower_bound(t.begin(), t.end(), xx,[](const auto &i, const auto &j){
        return i.fi < j;
    }) - t.begin() + 1;
    x = t.size() - x + 1;
    ll res = 0;
    for (; x; x -= x & -x){
        res += bit2[x];
    }
    return res;
}

void Init(){
    cin >> n >> k;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].fi >> a[i].se;
        b[i].low = min(a[i].fi, a[i].se);
        b[i].high = max(a[i].fi, a[i].se);
        b[i].idx = i;
    }
    for (int i = 1; i <= k; ++i){
        cin >> c[i];
        t.pb({c[i], i});
    }
    sort(t.begin(), t.end());
    t.resize(unique(t.begin(), t.end()) - t.begin());
    sort(b + 1, b + n + 1,[](const auto &i, const auto &j){
        return i.high < j.high;
    });
    int j = 1;
    for (int i = 1; i <= n; ++i){
        while (j <= k && t[j - 1].fi < b[i].high){
            update(t[j - 1].fi, t[j - 1].se);
            ++j;
        }
        flip[b[i].idx] = {get(b[i].low), b[i].idx, i};
    }
    sort(flip + 1, flip + n + 1,[](const auto &i, const auto &j){
        return i.val > j.val;
    });
    j = k;
    for (int i = 1; i <= n; ++i){
        while (j > 0 && j > flip[i].val){
            update2(c[j], 1);
            --j;
        }
        cnt[flip[i].idx1] = get2(b[flip[i].idx2].high);
        cnt1[flip[i].idx1] = flip[i].val;
    }
    ll answer = 0;
    for (int i = 1; i <= n; ++i){
        if (cnt1[i]){
            if (cnt[i] % 2) answer += min(a[i].fi, a[i].se);
            else answer += max(a[i].fi, a[i].se);
        }
        else{
            if (cnt[i] % 2) answer += a[i].se;
            else answer += a[i].fi;
        }
    }
    cout << answer;
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

fortune_telling2.cpp: In function 'void update2(int, int)':
fortune_telling2.cpp:63:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (; x <= t.size(); x += x & -x){
      |            ~~^~~~~~~~~~~
fortune_telling2.cpp: In function 'int get(int)':
fortune_telling2.cpp:73:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (; x <= t.size(); x += x & -x){
      |            ~~^~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 400 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 392 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 400 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 392 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 10 ms 1364 KB Output is correct
15 Correct 21 ms 2128 KB Output is correct
16 Correct 33 ms 2992 KB Output is correct
17 Correct 36 ms 3916 KB Output is correct
18 Correct 36 ms 3896 KB Output is correct
19 Correct 30 ms 3892 KB Output is correct
20 Correct 36 ms 3892 KB Output is correct
21 Correct 29 ms 3788 KB Output is correct
22 Correct 21 ms 3300 KB Output is correct
23 Correct 21 ms 3424 KB Output is correct
24 Correct 22 ms 3428 KB Output is correct
25 Correct 22 ms 3404 KB Output is correct
26 Correct 27 ms 3596 KB Output is correct
27 Correct 36 ms 3936 KB Output is correct
28 Correct 29 ms 4020 KB Output is correct
29 Correct 35 ms 3916 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 400 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 392 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 10 ms 1364 KB Output is correct
15 Correct 21 ms 2128 KB Output is correct
16 Correct 33 ms 2992 KB Output is correct
17 Correct 36 ms 3916 KB Output is correct
18 Correct 36 ms 3896 KB Output is correct
19 Correct 30 ms 3892 KB Output is correct
20 Correct 36 ms 3892 KB Output is correct
21 Correct 29 ms 3788 KB Output is correct
22 Correct 21 ms 3300 KB Output is correct
23 Correct 21 ms 3424 KB Output is correct
24 Correct 22 ms 3428 KB Output is correct
25 Correct 22 ms 3404 KB Output is correct
26 Correct 27 ms 3596 KB Output is correct
27 Correct 36 ms 3936 KB Output is correct
28 Correct 29 ms 4020 KB Output is correct
29 Correct 35 ms 3916 KB Output is correct
30 Runtime error 48 ms 8872 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -