oj.uz

Submission #1016437

# Submission time Handle Problem Language Result Execution time Memory
1016437 2024-07-08T05:14:02 Z Alish Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 315 ms 37056 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("tests.in" , "r" , stdin) ;

ll mod = 1e9+7;

const int N = 6e5+23;

int seg[4*N], fen[N];
int a[N], b[N], t[N];
vector<int> in[N];
ll ans;
int n, k, m;
void upd(int i, int x, int l=1, int r=m+1, int ind=0){
    if(r-l==1) {
        seg[ind]=x;
        return;
    }
    int mid=(r+l)>>1;
    if(i<mid) upd(i, x, l, mid, 2*ind+1);
    else upd(i, x, mid, r, 2*ind+2);
    seg[ind]=max(seg[2*ind+1], seg[2*ind+2]);
}

int get(int lx, int rx, int l=1, int r=m+1, int ind=0){
    if(lx>=r || rx<=l) return 0;
    if(lx<=l && rx>=r) return seg[ind];
    int mid=(r+l)>>1;
    return max(get(lx, rx, l, mid, 2*ind+1), get(lx, rx, mid, r, 2*ind+2));
}

void uupd(int x, int v){
    for(; x<N; x+=x&-x) fen[x]+=v;
}

int gget(int x){
    int ans=0;
    for(; x>0; x-=x&-x) ans+=fen[x];
    return ans;
}

int suff(int i){
    return gget(N-1)-gget(i-1);
}

int main()
{
    fast_io
    vector<int> vec;
    cin>>n>>k;
    for (int i=0; i<n; i++) {
        cin>>a[i]>>b[i];
        vec.pb(a[i]); vec.pb(b[i]);
    }
    t[0]=1;
    for (int i=1; i<=k; i++) {
        cin>>t[i];
        vec.pb(t[i]);
    }
    sort(all(vec)); vec.resize(unique(all(vec))-vec.begin());
    m=vec.size();
    for (int i=1; i<=k; i++){
        t[i]=lower_bound(all(vec), t[i])-vec.begin()+1;
        upd(t[i], i);
    }
    for (int i=0; i<n; i++){
        a[i]=lower_bound(all(vec), a[i])-vec.begin()+1;
        b[i]=lower_bound(all(vec), b[i])-vec.begin()+1;
        int num=get(min(a[i], b[i]), max(a[i], b[i]));
        if(num && b[i]>a[i]) swap(a[i], b[i]);
        in[num].pb(i);
    }
    for (int i=k; i>=0; i--){
        for (int j: in[i]){
            if(suff(max(a[j], b[j]))&1) swap(a[j], b[j]);
            ans+=vec[a[j]-1];
        }
        uupd(t[i], 1);
    }
    cout<<ans<<endl;



}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14564 KB Output is correct
2 Correct 7 ms 14616 KB Output is correct
3 Correct 7 ms 14684 KB Output is correct
4 Correct 7 ms 14684 KB Output is correct
5 Correct 7 ms 14624 KB Output is correct
6 Correct 7 ms 14684 KB Output is correct
7 Correct 7 ms 14652 KB Output is correct
8 Correct 7 ms 14680 KB Output is correct
9 Correct 7 ms 14680 KB Output is correct
10 Correct 7 ms 14632 KB Output is correct
11 Correct 7 ms 14688 KB Output is correct
12 Correct 7 ms 14684 KB Output is correct
13 Correct 9 ms 14684 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14564 KB Output is correct
2 Correct 7 ms 14616 KB Output is correct
3 Correct 7 ms 14684 KB Output is correct
4 Correct 7 ms 14684 KB Output is correct
5 Correct 7 ms 14624 KB Output is correct
6 Correct 7 ms 14684 KB Output is correct
7 Correct 7 ms 14652 KB Output is correct
8 Correct 7 ms 14680 KB Output is correct
9 Correct 7 ms 14680 KB Output is correct
10 Correct 7 ms 14632 KB Output is correct
11 Correct 7 ms 14688 KB Output is correct
12 Correct 7 ms 14684 KB Output is correct
13 Correct 9 ms 14684 KB Output is correct
14 Correct 21 ms 15452 KB Output is correct
15 Correct 28 ms 16340 KB Output is correct
16 Correct 41 ms 17620 KB Output is correct
17 Correct 53 ms 18388 KB Output is correct
18 Correct 53 ms 18340 KB Output is correct
19 Correct 54 ms 18280 KB Output is correct
20 Correct 55 ms 18388 KB Output is correct
21 Correct 53 ms 18328 KB Output is correct
22 Correct 41 ms 17628 KB Output is correct
23 Correct 39 ms 17112 KB Output is correct
24 Correct 40 ms 17108 KB Output is correct
25 Correct 41 ms 17872 KB Output is correct
26 Correct 45 ms 17868 KB Output is correct
27 Correct 47 ms 18128 KB Output is correct
28 Correct 43 ms 18132 KB Output is correct
29 Correct 52 ms 18356 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14564 KB Output is correct
2 Correct 7 ms 14616 KB Output is correct
3 Correct 7 ms 14684 KB Output is correct
4 Correct 7 ms 14684 KB Output is correct
5 Correct 7 ms 14624 KB Output is correct
6 Correct 7 ms 14684 KB Output is correct
7 Correct 7 ms 14652 KB Output is correct
8 Correct 7 ms 14680 KB Output is correct
9 Correct 7 ms 14680 KB Output is correct
10 Correct 7 ms 14632 KB Output is correct
11 Correct 7 ms 14688 KB Output is correct
12 Correct 7 ms 14684 KB Output is correct
13 Correct 9 ms 14684 KB Output is correct
14 Correct 21 ms 15452 KB Output is correct
15 Correct 28 ms 16340 KB Output is correct
16 Correct 41 ms 17620 KB Output is correct
17 Correct 53 ms 18388 KB Output is correct
18 Correct 53 ms 18340 KB Output is correct
19 Correct 54 ms 18280 KB Output is correct
20 Correct 55 ms 18388 KB Output is correct
21 Correct 53 ms 18328 KB Output is correct
22 Correct 41 ms 17628 KB Output is correct
23 Correct 39 ms 17112 KB Output is correct
24 Correct 40 ms 17108 KB Output is correct
25 Correct 41 ms 17872 KB Output is correct
26 Correct 45 ms 17868 KB Output is correct
27 Correct 47 ms 18128 KB Output is correct
28 Correct 43 ms 18132 KB Output is correct
29 Correct 52 ms 18356 KB Output is correct
30 Correct 101 ms 21452 KB Output is correct
31 Correct 140 ms 25320 KB Output is correct
32 Correct 191 ms 27592 KB Output is correct
33 Correct 299 ms 36800 KB Output is correct
34 Correct 91 ms 20868 KB Output is correct
35 Correct 301 ms 36664 KB Output is correct
36 Correct 305 ms 36748 KB Output is correct
37 Correct 315 ms 36540 KB Output is correct
38 Correct 297 ms 36680 KB Output is correct
39 Correct 288 ms 36736 KB Output is correct
40 Correct 308 ms 37056 KB Output is correct
41 Correct 300 ms 36540 KB Output is correct
42 Correct 278 ms 36484 KB Output is correct
43 Correct 188 ms 31936 KB Output is correct
44 Correct 202 ms 32356 KB Output is correct
45 Correct 202 ms 33680 KB Output is correct
46 Correct 200 ms 29628 KB Output is correct
47 Correct 184 ms 26828 KB Output is correct
48 Correct 219 ms 31936 KB Output is correct
49 Correct 227 ms 31932 KB Output is correct