oj.uz

Submission #1112227

# Submission time Handle Problem Language Result Execution time Memory
1112227 2024-11-13T20:23:44 Z PagodePaiva Fortune Telling 2 (JOI14_fortune_telling2) C++17
4 / 100
 3000 ms 17608 KB 
#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second

using namespace std;

const int N = 200010;
const int B = 200;
int v[N][2];
int blocks[N];

struct Segtree{
    pair <int, int> tree[4*N]; int lazy[4*N];
    pair <int, int> join(pair <int, int> a, pair <int, int> b){
        return {max(a.fr, b.fr), max(a.sc, b.sc)};
    }
    void unlazy(int node, int l, int r){
        if(lazy[node]%2) swap(tree[node].fr, tree[node].sc);
        if(l != r){
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    void build(int node, int l, int r){
        lazy[node] = 0;
        if(l == r){
            tree[node] = {v[l][0], v[l][1]};
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
    }
    void update(int node, int l, int r, int tl, int tr, int val){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(l <= tl and tr <= r){
            if(tree[node].first <= val) {
                lazy[node]++;
                unlazy(node, tl, tr);
                return;
            }
            else{
                int mid = (tl+tr)/2;
                if(tl == tr) return;
                update(2*node, l, r, tl, mid, val);
                update(2*node+1, l, r, mid+1, tr, val);
                tree[node] = join(tree[2*node], tree[2*node+1]);
            }
            return;
        }
        int mid = (tl+tr)/2;
        update(2*node, l, r, tl, mid, val);
        update(2*node+1, l, r, mid+1, tr, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    pair <int, int> query(int node, int l, int r, int tl, int tr){
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return {0, 0};
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} seg;

bool comp2(array <int, 3> a, array <int, 3> b){
    if(blocks[a[2]] > blocks[b[2]]) return false;
    if(blocks[a[2]] < blocks[b[2]]) return true;
    if(max(a[0], a[1]) < max(b[0], b[1])) return true;
    return false;
}

bool comp(array <int, 3> a, array <int, 3> b){
    if(min(a[0], a[1]) < min(b[0], b[1])) return true;
    return false;
}

int32_t main(){
    srand(time(0));
    ios::sync_with_stdio(false); cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector <array <int, 3>> vv;
    for(int i = 1;i <= n;i++){
        int a, b;
        cin >> a >> b;
        vv.push_back({a, b, i});
    }
    sort(vv.begin(),vv.end());
    for(int i = 0;i < n;i++){
        v[i+1][0] = vv[i][0];
        v[i+1][1] = vv[i][1];
        //cout << v[i+1][0] << ' ' << v[i+1][1] << '\n';
    }
    seg.build(1,1, n);
    for(int i = 0;i < k;i++){
        int q;
        cin >> q;
        seg.update(1, 1, n, 1, n, q);
    }
    int res = 0;
    for(int i = 1;i <= n;i++){
        res += seg.query(1, i, i, 1, n).first;   
    }
    cout << res << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16976 KB Output is correct
2 Correct 10 ms 16976 KB Output is correct
3 Correct 12 ms 16976 KB Output is correct
4 Correct 12 ms 16976 KB Output is correct
5 Correct 12 ms 16992 KB Output is correct
6 Correct 11 ms 16976 KB Output is correct
7 Correct 9 ms 16976 KB Output is correct
8 Correct 12 ms 17104 KB Output is correct
9 Correct 13 ms 16976 KB Output is correct
10 Correct 10 ms 17100 KB Output is correct
11 Correct 8 ms 17144 KB Output is correct
12 Correct 7 ms 17104 KB Output is correct
13 Correct 8 ms 16976 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16976 KB Output is correct
2 Correct 10 ms 16976 KB Output is correct
3 Correct 12 ms 16976 KB Output is correct
4 Correct 12 ms 16976 KB Output is correct
5 Correct 12 ms 16992 KB Output is correct
6 Correct 11 ms 16976 KB Output is correct
7 Correct 9 ms 16976 KB Output is correct
8 Correct 12 ms 17104 KB Output is correct
9 Correct 13 ms 16976 KB Output is correct
10 Correct 10 ms 17100 KB Output is correct
11 Correct 8 ms 17144 KB Output is correct
12 Correct 7 ms 17104 KB Output is correct
13 Correct 8 ms 16976 KB Output is correct
14 Correct 1012 ms 17228 KB Output is correct
15 Execution timed out 3039 ms 17608 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16976 KB Output is correct
2 Correct 10 ms 16976 KB Output is correct
3 Correct 12 ms 16976 KB Output is correct
4 Correct 12 ms 16976 KB Output is correct
5 Correct 12 ms 16992 KB Output is correct
6 Correct 11 ms 16976 KB Output is correct
7 Correct 9 ms 16976 KB Output is correct
8 Correct 12 ms 17104 KB Output is correct
9 Correct 13 ms 16976 KB Output is correct
10 Correct 10 ms 17100 KB Output is correct
11 Correct 8 ms 17144 KB Output is correct
12 Correct 7 ms 17104 KB Output is correct
13 Correct 8 ms 16976 KB Output is correct
14 Correct 1012 ms 17228 KB Output is correct
15 Execution timed out 3039 ms 17608 KB Time limit exceeded
16 Halted 0 ms 0 KB -