oj.uz

Submission #786746

# Submission time Handle Problem Language Result Execution time Memory
786746 2023-07-18T12:24:19 Z winter0101 Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 778 ms 68480 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
using pil=pair<int,long long>;
using pll=pair<long long,long long>;
const int maxn=2e5+9;
int st[maxn*4*3];
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
    st[id]=val;
    return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
st[id]=max(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return st[id];
int mid=(l+r)/2;
return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int m;
int bit[maxn*3];
void add(int pos,int val){
for(;pos<=m;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
int get(int pos){
if (pos==0)return 0;
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
int a[maxn*3],b[maxn*3];
int c[maxn*3];
bool flip[maxn*3];
int d[maxn*3];
int ren[maxn*3];
vector<int>query[maxn*3];
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("usaco.INP","r",stdin);
    //freopen("usaco.OUT","w",stdout);
    int n,q;
    cin>>n>>q;
    vector<int>num;
    num.pb(0);
    for1(i,1,n){
    cin>>a[i]>>b[i];
    num.pb(a[i]);
    num.pb(b[i]);
    }
    for1(i,1,q){
    cin>>c[i];
    num.pb(c[i]);
    }
    sort(all(num));
    map<int,int>nen;
    m=0;
    for1(i,1,sz(num)-1){
    if (num[i]>num[i-1]){
        nen[num[i]]=nen[num[i-1]]+1;
        m=nen[num[i]];
        ren[m]=num[i];
    }
    }
    for1(i,1,n){
    a[i]=nen[a[i]];
    b[i]=nen[b[i]];
    }
    for1(i,1,q)c[i]=nen[c[i]];
    for1(i,1,q){
    update(1,1,m,c[i],i);
    }
    for1(i,1,n){
    int x=min(a[i],b[i]),y=max(a[i],b[i]);
    int vcl=get(1,1,m,x,y-1);
    if (vcl==0){
        continue;
    }
    query[vcl].pb(i);
    if (a[i]<b[i]){
        flip[i]=1;
    }
    }
    for1(i,1,q){
    add(c[i],1);
    for (auto v:query[i]){
        d[v]=-get(m)+get(max(a[v],b[v])-1);
    }
    }
    long long sum=0;
    for1(i,1,n){
    d[i]+=get(m)-get(max(a[i],b[i])-1);
    d[i]%=2;
    flip[i]^=d[i];
    if (!flip[i]){
       sum+=ren[a[i]];
    }
    else sum+=ren[b[i]];
    }
    cout<<sum;
 
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14548 KB Output is correct
2 Correct 10 ms 14556 KB Output is correct
3 Correct 9 ms 14688 KB Output is correct
4 Correct 8 ms 14676 KB Output is correct
5 Correct 9 ms 14628 KB Output is correct
6 Correct 9 ms 14688 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14716 KB Output is correct
9 Correct 9 ms 14676 KB Output is correct
10 Correct 9 ms 14548 KB Output is correct
11 Correct 8 ms 14564 KB Output is correct
12 Correct 9 ms 14548 KB Output is correct
13 Correct 8 ms 14684 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14548 KB Output is correct
2 Correct 10 ms 14556 KB Output is correct
3 Correct 9 ms 14688 KB Output is correct
4 Correct 8 ms 14676 KB Output is correct
5 Correct 9 ms 14628 KB Output is correct
6 Correct 9 ms 14688 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14716 KB Output is correct
9 Correct 9 ms 14676 KB Output is correct
10 Correct 9 ms 14548 KB Output is correct
11 Correct 8 ms 14564 KB Output is correct
12 Correct 9 ms 14548 KB Output is correct
13 Correct 8 ms 14684 KB Output is correct
14 Correct 27 ms 16988 KB Output is correct
15 Correct 52 ms 19464 KB Output is correct
16 Correct 78 ms 22260 KB Output is correct
17 Correct 120 ms 24588 KB Output is correct
18 Correct 117 ms 24616 KB Output is correct
19 Correct 105 ms 24600 KB Output is correct
20 Correct 104 ms 24520 KB Output is correct
21 Correct 104 ms 24656 KB Output is correct
22 Correct 75 ms 21812 KB Output is correct
23 Correct 65 ms 20356 KB Output is correct
24 Correct 66 ms 19396 KB Output is correct
25 Correct 78 ms 22680 KB Output is correct
26 Correct 71 ms 21664 KB Output is correct
27 Correct 84 ms 22380 KB Output is correct
28 Correct 87 ms 22320 KB Output is correct
29 Correct 96 ms 23512 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14548 KB Output is correct
2 Correct 10 ms 14556 KB Output is correct
3 Correct 9 ms 14688 KB Output is correct
4 Correct 8 ms 14676 KB Output is correct
5 Correct 9 ms 14628 KB Output is correct
6 Correct 9 ms 14688 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14716 KB Output is correct
9 Correct 9 ms 14676 KB Output is correct
10 Correct 9 ms 14548 KB Output is correct
11 Correct 8 ms 14564 KB Output is correct
12 Correct 9 ms 14548 KB Output is correct
13 Correct 8 ms 14684 KB Output is correct
14 Correct 27 ms 16988 KB Output is correct
15 Correct 52 ms 19464 KB Output is correct
16 Correct 78 ms 22260 KB Output is correct
17 Correct 120 ms 24588 KB Output is correct
18 Correct 117 ms 24616 KB Output is correct
19 Correct 105 ms 24600 KB Output is correct
20 Correct 104 ms 24520 KB Output is correct
21 Correct 104 ms 24656 KB Output is correct
22 Correct 75 ms 21812 KB Output is correct
23 Correct 65 ms 20356 KB Output is correct
24 Correct 66 ms 19396 KB Output is correct
25 Correct 78 ms 22680 KB Output is correct
26 Correct 71 ms 21664 KB Output is correct
27 Correct 84 ms 22380 KB Output is correct
28 Correct 87 ms 22320 KB Output is correct
29 Correct 96 ms 23512 KB Output is correct
30 Correct 226 ms 32444 KB Output is correct
31 Correct 307 ms 40816 KB Output is correct
32 Correct 468 ms 48452 KB Output is correct
33 Correct 745 ms 68360 KB Output is correct
34 Correct 204 ms 30872 KB Output is correct
35 Correct 752 ms 68248 KB Output is correct
36 Correct 744 ms 68140 KB Output is correct
37 Correct 762 ms 68036 KB Output is correct
38 Correct 734 ms 68148 KB Output is correct
39 Correct 777 ms 68044 KB Output is correct
40 Correct 676 ms 68480 KB Output is correct
41 Correct 778 ms 68056 KB Output is correct
42 Correct 744 ms 68016 KB Output is correct
43 Correct 510 ms 63216 KB Output is correct
44 Correct 485 ms 63752 KB Output is correct
45 Correct 483 ms 65020 KB Output is correct
46 Correct 396 ms 45804 KB Output is correct
47 Correct 310 ms 37920 KB Output is correct
48 Correct 489 ms 53124 KB Output is correct
49 Correct 457 ms 53312 KB Output is correct