oj.uz

Submission #49618

# Submission time Handle Problem Language Result Execution time Memory
49618 2018-06-01T05:51:00 Z mra2322001 Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 2000 ms 3328 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i=(0); i<n; i++)
#define f1(i, n) for(int i=(1); i<=n; i++)

using namespace std;
typedef long long ll;
const int N = 200002;
struct data{
    int x, id;
    bool operator <(data g){
        return x < g.x;
    }
} a[N], b[N];

int n, k, t[N], answer[N];

void up(int node, int l, int r, int i, int val){
    if(r < i || l > i) return ;
    if(l==r){
        t[node] = val;
        return ;
    }
    int m = (l + r)/2;
    up(node*2, l, m, i, val);
    up(node*2+1, m + 1, r, i, val);
    t[node] = max(t[2*node], t[2*node+1]);
}

int get2(int node, int l, int r, int i, int j){
    if(r < i || l > j) return 0;
    if(l >= i && r <= j) return t[node];
    int m = (l + r)/2;
    return max(get2(node*2, l, m, i, j), get2(node*2+1, m + 1, r, i, j));
}

void update(int x, int val){
    up(1, 1, k, x, val);
}

int get1(int x, int y){
    return get2(1, 1, k, x, y);
}

int Ans(int x){if(x==1) return 2;return 1;}
main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> k;
    f1(i, n){
        cin >> a[i].x >> b[i].x;
        b[i].id = a[i].id = i;
    }

    f1(i, k){
        int u; cin >> u;
        update(i, u);
    }
    vector <pair <int, int> > save;
    f1(i, n){
        /// assume a[i] could be ans[1]
        /// find 1 and 2
        while(save.size()) save.pop_back();
        int k1 = k, k2 = k;
        while(1){
            int p1, p2;
            int l = 1, r = k1, ans = 0;
            while(l <= r){
                int mid = (l + r)/2;
                if(get1(mid, k1) >= a[i].x) ans = mid, l = mid + 1;
                else r = mid - 1;
            } p1 = ans;
            l = 1, r = k2, ans = 0;
            while(l <= r){
                int mid = (l + r)/2;
                if(get1(mid, k2) >= b[i].x) ans = mid, l = mid + 1;
                else r = mid - 1;
            } p2 = ans;
            save.push_back(make_pair(p1, p2));
            if(p1 != p2) break;
            if(p1==0) break;
            k1 = p1 - 1, k2 = p2 - 1;
        }
        int y = 2; /// now i belong to Ans(2)
        if(save.size() == 1){
            if(save[0].first > save[0].second) answer[i] = Ans(1);
            else answer[i] = Ans(2);
        }
        else{
            for(int j = save.size() - 1; j >= 0; j--){
                if(min(save[j].first, save[j].second)){
                    if(save[j].first==save[j].second){
                        if(y==2) y = 1;
                        else y = 2;
                    }
                    else{
                        if(save[j].first > save[j].second){
                            y = 1;
                        }
                        else{
                            y = 2;
                        }
                    }
                }
            }
            answer[i] = Ans(y);
        }
    }
    ll res = 0;
    f1(i, n){
        if(answer[i]==2) res += ll(b[i].x);
        else res += ll(a[i].x);
    }
    cout << res;
}

Compilation message

fortune_telling2.cpp:45:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 484 KB Output is correct
3 Correct 14 ms 688 KB Output is correct
4 Correct 19 ms 688 KB Output is correct
5 Correct 18 ms 704 KB Output is correct
6 Correct 5 ms 704 KB Output is correct
7 Correct 381 ms 868 KB Output is correct
8 Correct 4 ms 868 KB Output is correct
9 Correct 4 ms 868 KB Output is correct
10 Correct 14 ms 868 KB Output is correct
11 Correct 811 ms 868 KB Output is correct
12 Correct 825 ms 868 KB Output is correct
13 Correct 979 ms 868 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 1148 KB Output is correct
2 Correct 960 ms 1516 KB Output is correct
3 Correct 1790 ms 2044 KB Output is correct
4 Execution timed out 2041 ms 2436 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 3328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -