oj.uz

Submission #52760

# Submission time Handle Problem Language Result Execution time Memory
52760 2018-06-26T16:54:54 Z Smelskiy Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 3000 ms 1516 KB 
#include <bits/stdc++.h>
using namespace std;




int n,m;
int q[2000005];
int t1[2000005];
int t2[2000005];
pair<int,int> a[200005];
int sz;


inline void push(int x) {
    if (!q[x]) return;
    q[x+x]^=1;
    q[x+x+1]^=1;
    q[x]=0;
    swap(t1[x+x],t2[x+x]);
    swap(t1[x+x+1],t2[x+x+1]);
}

void dfs(int l,int r,int x,int y) {
    if (t1[x]<=y) {
        swap(t1[x],t2[x]);
        q[x]^=1;
        return;
    }
    if (l==r) return;
    int mid=(l+r)>>1;
    push(x);
    dfs(l,mid,x+x,y);
    dfs(mid+1,r,x+x+1,y);
    t1[x]=max(t1[x+x],t1[x+x+1]);
    t2[x]=max(t2[x+x],t2[x+x+1]);
}

long long ans=0;
void solve(int l,int r,int x) {
    if (l>n) return;
    if (l==r) {
        ans+=t1[x];
        return;
    }
    push(x);
    int mid=(l+r)>>1;
    solve(l,mid,x+x);
    solve(mid+1,r,x+x+1);
}

inline bool cmp(pair<int,int> x,pair<int,int> y) {
    return max(x.first,x.second)<max(y.first,y.second);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;++i) {
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+n+1,cmp);
    sz=1;
    while (sz<n) sz+=sz;
    for (int i=1;i<=n;++i) {
        t1[sz+i-1]=a[i].first;
        t2[sz+i-1]=a[i].second;
    }
    for (int i=sz-1;i>0;--i) {
        t1[i]=max(t1[i+i],t1[i+i+1]);
        t2[i]=max(t2[i+i],t2[i+i+1]);
    }
    int x;
    for (int i=1;i<=m;++i) {
        cin>>x;
        dfs(1,sz,1,x);
    }
    solve(1,sz,1);
    cout<<ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 380 KB Output is correct
2 Correct 7 ms 488 KB Output is correct
3 Correct 11 ms 488 KB Output is correct
4 Correct 12 ms 488 KB Output is correct
5 Correct 11 ms 636 KB Output is correct
6 Correct 12 ms 636 KB Output is correct
7 Correct 10 ms 636 KB Output is correct
8 Correct 20 ms 692 KB Output is correct
9 Correct 15 ms 692 KB Output is correct
10 Correct 9 ms 692 KB Output is correct
11 Correct 8 ms 692 KB Output is correct
12 Correct 8 ms 692 KB Output is correct
13 Correct 8 ms 692 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 380 KB Output is correct
2 Correct 7 ms 488 KB Output is correct
3 Correct 11 ms 488 KB Output is correct
4 Correct 12 ms 488 KB Output is correct
5 Correct 11 ms 636 KB Output is correct
6 Correct 12 ms 636 KB Output is correct
7 Correct 10 ms 636 KB Output is correct
8 Correct 20 ms 692 KB Output is correct
9 Correct 15 ms 692 KB Output is correct
10 Correct 9 ms 692 KB Output is correct
11 Correct 8 ms 692 KB Output is correct
12 Correct 8 ms 692 KB Output is correct
13 Correct 8 ms 692 KB Output is correct
14 Correct 875 ms 1040 KB Output is correct
15 Execution timed out 3041 ms 1516 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 380 KB Output is correct
2 Correct 7 ms 488 KB Output is correct
3 Correct 11 ms 488 KB Output is correct
4 Correct 12 ms 488 KB Output is correct
5 Correct 11 ms 636 KB Output is correct
6 Correct 12 ms 636 KB Output is correct
7 Correct 10 ms 636 KB Output is correct
8 Correct 20 ms 692 KB Output is correct
9 Correct 15 ms 692 KB Output is correct
10 Correct 9 ms 692 KB Output is correct
11 Correct 8 ms 692 KB Output is correct
12 Correct 8 ms 692 KB Output is correct
13 Correct 8 ms 692 KB Output is correct
14 Correct 875 ms 1040 KB Output is correct
15 Execution timed out 3041 ms 1516 KB Time limit exceeded
16 Halted 0 ms 0 KB -