oj.uz

Submission #723758

# Submission time Handle Problem Language Result Execution time Memory
723758 2023-04-14T09:18:50 Z kkts Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 162 ms 27632 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 = 2e5 + 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 4 ms 5076 KB Output is correct
2 Correct 5 ms 5148 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct
6 Correct 6 ms 5144 KB Output is correct
7 Correct 8 ms 5204 KB Output is correct
8 Correct 6 ms 5204 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 5 ms 5156 KB Output is correct
12 Correct 5 ms 5204 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 5 ms 5148 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct
6 Correct 6 ms 5144 KB Output is correct
7 Correct 8 ms 5204 KB Output is correct
8 Correct 6 ms 5204 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 5 ms 5156 KB Output is correct
12 Correct 5 ms 5204 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct
14 Correct 27 ms 6984 KB Output is correct
15 Correct 57 ms 8996 KB Output is correct
16 Correct 85 ms 11516 KB Output is correct
17 Correct 115 ms 12828 KB Output is correct
18 Correct 117 ms 12940 KB Output is correct
19 Correct 108 ms 12920 KB Output is correct
20 Correct 117 ms 12848 KB Output is correct
21 Correct 105 ms 12852 KB Output is correct
22 Correct 76 ms 12096 KB Output is correct
23 Correct 84 ms 10976 KB Output is correct
24 Correct 73 ms 10836 KB Output is correct
25 Correct 79 ms 12164 KB Output is correct
26 Correct 94 ms 11144 KB Output is correct
27 Correct 113 ms 11788 KB Output is correct
28 Correct 100 ms 11996 KB Output is correct
29 Correct 128 ms 12348 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 5 ms 5148 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct
6 Correct 6 ms 5144 KB Output is correct
7 Correct 8 ms 5204 KB Output is correct
8 Correct 6 ms 5204 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 5 ms 5156 KB Output is correct
12 Correct 5 ms 5204 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct
14 Correct 27 ms 6984 KB Output is correct
15 Correct 57 ms 8996 KB Output is correct
16 Correct 85 ms 11516 KB Output is correct
17 Correct 115 ms 12828 KB Output is correct
18 Correct 117 ms 12940 KB Output is correct
19 Correct 108 ms 12920 KB Output is correct
20 Correct 117 ms 12848 KB Output is correct
21 Correct 105 ms 12852 KB Output is correct
22 Correct 76 ms 12096 KB Output is correct
23 Correct 84 ms 10976 KB Output is correct
24 Correct 73 ms 10836 KB Output is correct
25 Correct 79 ms 12164 KB Output is correct
26 Correct 94 ms 11144 KB Output is correct
27 Correct 113 ms 11788 KB Output is correct
28 Correct 100 ms 11996 KB Output is correct
29 Correct 128 ms 12348 KB Output is correct
30 Runtime error 162 ms 27632 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -