oj.uz

Submission #49619

# Submission time Handle Problem Language Result Execution time Memory
49619 2018-06-01T05:51:48 Z mra2322001 Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 2000 ms 7140 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*4], 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 4 ms 376 KB Output is correct
2 Correct 15 ms 488 KB Output is correct
3 Correct 15 ms 544 KB Output is correct
4 Correct 21 ms 544 KB Output is correct
5 Correct 20 ms 552 KB Output is correct
6 Correct 6 ms 552 KB Output is correct
7 Correct 395 ms 644 KB Output is correct
8 Correct 4 ms 644 KB Output is correct
9 Correct 3 ms 644 KB Output is correct
10 Correct 13 ms 644 KB Output is correct
11 Correct 968 ms 664 KB Output is correct
12 Correct 944 ms 724 KB Output is correct
13 Correct 958 ms 724 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 1164 KB Output is correct
2 Correct 1053 ms 1480 KB Output is correct
3 Correct 1906 ms 2004 KB Output is correct
4 Execution timed out 2070 ms 2500 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 2916 KB Output is correct
2 Execution timed out 2062 ms 7140 KB Time limit exceeded
3 Halted 0 ms 0 KB -