oj.uz

Submission #49617

# Submission time Handle Problem Language Result Execution time Memory
49617 2018-06-01T05:42:28 Z mra2322001 Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 2000 ms 6244 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 10 ms 488 KB Output is correct
3 Correct 14 ms 560 KB Output is correct
4 Correct 24 ms 764 KB Output is correct
5 Correct 20 ms 812 KB Output is correct
6 Correct 9 ms 856 KB Output is correct
7 Correct 394 ms 916 KB Output is correct
8 Correct 7 ms 964 KB Output is correct
9 Correct 4 ms 964 KB Output is correct
10 Correct 13 ms 1072 KB Output is correct
11 Correct 959 ms 1100 KB Output is correct
12 Correct 1062 ms 1100 KB Output is correct
13 Correct 1012 ms 1168 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 1660 KB Output is correct
2 Correct 1070 ms 2604 KB Output is correct
3 Correct 1905 ms 3980 KB Output is correct
4 Execution timed out 2045 ms 5416 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 6244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -