oj.uz

Submission #723760

# Submission time Handle Problem Language Result Execution time Memory
723760 2023-04-14T09:19:16 Z kkts Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 730 ms 60360 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 6e5 + 5, mod = 1e9 + 7; // !
int fw[N], a[N], b[N], c[N], t[4 * N], m;
vector<int> X[N];
void upd(int id) {
    for(id; id <= m; id += id & (-id)) fw[id] ^= 1;
}
int get(int id) {
    int ans = 0;
    for(id; id >= 1; id -= id & (-id)) ans ^= fw[id];
    return ans;
}
bool cmp(int x, int y) {
    return (max(a[x], b[x]) < max(a[y], b[y]));
}
int merge(int i, int j) {
    return (max(a[i], b[i]) >= max(a[j], b[j]) ? i : j);
}
void build(int u, int l, int r) {
    if(l == r) {
        t[u] = (X[l].size() ? X[l].back() : 0);
        return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
void rem(int u, int id, int l, int r)  {
    if(l > id || r < id) return;
    if(l == r) {
        X[l].pop_back();
        t[u] = (X[l].size() ? X[l].back() : 0);
        return;
    }
    int mid = (l + r) / 2;
    rem(2 * u, id, l, mid); rem(2 * u + 1, id, mid + 1, r);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
int get(int u, int st, int en, int l, int r) {
    if(l > en || r < st) return 0;
    if(st <= l && r <= en) return t[u];
    int mid = (l + r) / 2;
    return merge(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
main(){
    int n, k;
    cin >> n >> k;
    vector<int> x;
    vector<int> A(n + 1), B(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        A[i] = a[i]; B[i] = b[i];
        x.push_back(a[i]);
        x.push_back(b[i]);
    }
    for(int i = 1; i <= k; i++) {
        cin >> c[i];
        x.push_back(c[i]);
    }
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    for(int i = 1; i <= n; i++)
    a[i] = lower_bound(x.begin(), x.end(), a[i]) - x.begin() + 1,
    b[i] = lower_bound(x.begin(), x.end(), b[i]) - x.begin() + 1,
    X[min(a[i], b[i])].push_back(i);
    for(int i = 1; i <= x.size(); i++) sort(X[i].begin(), X[i].end(), cmp);
    build(1, 1, x.size());
    m = x.size();
    int ans = 0;
    for(int i = k; i >= 0; i--) {
        c[i] = lower_bound(x.begin(), x.end(), c[i]) - x.begin() + 1;
        while(true) {
            int id = get(1, 1, (!i ? m : c[i]), 1, m);
            if(max(a[id], b[id]) > (!i ? 0 : c[i])) {
                if(i) ans += (get(min(a[id], b[id])) ? min(A[id], B[id]) : max(A[id], B[id]));
                else ans += (get(min(a[id], b[id])) == 0 ? A[id] : B[id]);
                rem(1, min(a[id], b[id]), 1, m);
            } else break;
        }
        upd(1);
        upd(c[i] + 1);
    }
    cout << ans;
}

Compilation message

fortune_telling2.cpp: In function 'void upd(long long int)':
fortune_telling2.cpp:11:9: warning: statement has no effect [-Wunused-value]
   11 |     for(id; id <= m; id += id & (-id)) fw[id] ^= 1;
      |         ^~
fortune_telling2.cpp: In function 'long long int get(long long int)':
fortune_telling2.cpp:15:9: warning: statement has no effect [-Wunused-value]
   15 |     for(id; id >= 1; id -= id & (-id)) ans ^= fw[id];
      |         ^~
fortune_telling2.cpp: At global scope:
fortune_telling2.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:71:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 1; i <= x.size(); i++) sort(X[i].begin(), X[i].end(), cmp);
      |                    ~~^~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14496 KB Output is correct
2 Correct 10 ms 14436 KB Output is correct
3 Correct 10 ms 14548 KB Output is correct
4 Correct 11 ms 14548 KB Output is correct
5 Correct 10 ms 14500 KB Output is correct
6 Correct 10 ms 14548 KB Output is correct
7 Correct 10 ms 14548 KB Output is correct
8 Correct 10 ms 14588 KB Output is correct
9 Correct 9 ms 14584 KB Output is correct
10 Correct 9 ms 14548 KB Output is correct
11 Correct 10 ms 14504 KB Output is correct
12 Correct 10 ms 14456 KB Output is correct
13 Correct 9 ms 14548 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14496 KB Output is correct
2 Correct 10 ms 14436 KB Output is correct
3 Correct 10 ms 14548 KB Output is correct
4 Correct 11 ms 14548 KB Output is correct
5 Correct 10 ms 14500 KB Output is correct
6 Correct 10 ms 14548 KB Output is correct
7 Correct 10 ms 14548 KB Output is correct
8 Correct 10 ms 14588 KB Output is correct
9 Correct 9 ms 14584 KB Output is correct
10 Correct 9 ms 14548 KB Output is correct
11 Correct 10 ms 14504 KB Output is correct
12 Correct 10 ms 14456 KB Output is correct
13 Correct 9 ms 14548 KB Output is correct
14 Correct 33 ms 16104 KB Output is correct
15 Correct 60 ms 17740 KB Output is correct
16 Correct 88 ms 19968 KB Output is correct
17 Correct 119 ms 21096 KB Output is correct
18 Correct 122 ms 21216 KB Output is correct
19 Correct 113 ms 21180 KB Output is correct
20 Correct 120 ms 21264 KB Output is correct
21 Correct 116 ms 21056 KB Output is correct
22 Correct 81 ms 20800 KB Output is correct
23 Correct 82 ms 19800 KB Output is correct
24 Correct 77 ms 19524 KB Output is correct
25 Correct 82 ms 20880 KB Output is correct
26 Correct 92 ms 19476 KB Output is correct
27 Correct 100 ms 20176 KB Output is correct
28 Correct 99 ms 20160 KB Output is correct
29 Correct 107 ms 20512 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14496 KB Output is correct
2 Correct 10 ms 14436 KB Output is correct
3 Correct 10 ms 14548 KB Output is correct
4 Correct 11 ms 14548 KB Output is correct
5 Correct 10 ms 14500 KB Output is correct
6 Correct 10 ms 14548 KB Output is correct
7 Correct 10 ms 14548 KB Output is correct
8 Correct 10 ms 14588 KB Output is correct
9 Correct 9 ms 14584 KB Output is correct
10 Correct 9 ms 14548 KB Output is correct
11 Correct 10 ms 14504 KB Output is correct
12 Correct 10 ms 14456 KB Output is correct
13 Correct 9 ms 14548 KB Output is correct
14 Correct 33 ms 16104 KB Output is correct
15 Correct 60 ms 17740 KB Output is correct
16 Correct 88 ms 19968 KB Output is correct
17 Correct 119 ms 21096 KB Output is correct
18 Correct 122 ms 21216 KB Output is correct
19 Correct 113 ms 21180 KB Output is correct
20 Correct 120 ms 21264 KB Output is correct
21 Correct 116 ms 21056 KB Output is correct
22 Correct 81 ms 20800 KB Output is correct
23 Correct 82 ms 19800 KB Output is correct
24 Correct 77 ms 19524 KB Output is correct
25 Correct 82 ms 20880 KB Output is correct
26 Correct 92 ms 19476 KB Output is correct
27 Correct 100 ms 20176 KB Output is correct
28 Correct 99 ms 20160 KB Output is correct
29 Correct 107 ms 20512 KB Output is correct
30 Correct 213 ms 24140 KB Output is correct
31 Correct 322 ms 34936 KB Output is correct
32 Correct 417 ms 40612 KB Output is correct
33 Correct 717 ms 60124 KB Output is correct
34 Correct 196 ms 25164 KB Output is correct
35 Correct 673 ms 60256 KB Output is correct
36 Correct 710 ms 60144 KB Output is correct
37 Correct 730 ms 60208 KB Output is correct
38 Correct 687 ms 60360 KB Output is correct
39 Correct 704 ms 60140 KB Output is correct
40 Correct 681 ms 59932 KB Output is correct
41 Correct 655 ms 60272 KB Output is correct
42 Correct 687 ms 60020 KB Output is correct
43 Correct 509 ms 57432 KB Output is correct
44 Correct 520 ms 57760 KB Output is correct
45 Correct 491 ms 58488 KB Output is correct
46 Correct 428 ms 47784 KB Output is correct
47 Correct 411 ms 42816 KB Output is correct
48 Correct 535 ms 46432 KB Output is correct
49 Correct 557 ms 47136 KB Output is correct