oj.uz

Submission #1100721

# Submission time Handle Problem Language Result Execution time Memory
1100721 2024-10-14T13:54:51 Z vjudge1 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 204 ms 51016 KB 
#include<bits/stdc++.h>
using namespace std;
#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 bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+69;
const ll offset=2e5;
const ll inf=1e18;
const int base=350;
const ll mod=998244353;

int n,k;
int a[maxn],b[maxn],t[maxn];
pii c[maxn];
int rmq[maxn][19];
vector<pii> qr[maxn];
int dd[maxn];

int st[maxn];
void Update(int u)
{
    for(;u<=k;u+=u&-u) st[u]+=1;
}
int Get1(int u)
{
    int r=0;
    for(;u>0;u-=u&-u) r+=st[u];
    return r;
}
int Get(int l,int r)
{
    return Get1(r)-Get1(l-1);
}

int Get_max(int l,int r)
{
    int lg=__lg(r-l+1);
    return max(rmq[l][lg],rmq[r-(1<<lg)+1][lg]);
}

void sol()
{
    cin >> n>>k;
    for1(i,1,n) cin >> a[i]>> b[i];
    for1(i,1,k)
    {
        cin >> t[i];
        c[i]={t[i],i};
    }
    sort(c+1,c+1+k);
    for1(i,1,k) rmq[i][0]=c[i].se;
    for1(j,1,18) for1(i,1,k-(1<<j)+1) rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
    for1(i,1,n)
    {
        int l=min(a[i],b[i]);
        int r=max(a[i],b[i]);
        int cl= upper_bound(c+1,c+1+k,make_pair(l,-1LL))-c;
        int cr=upper_bound(c+1,c+1+k,make_pair(r,-1LL))-c-1;
        int j=0;
        if (cl<=cr)
        {
            j=Get_max(cl,cr);
            if (a[i]<b[i]) swap(a[i],b[i]);
        }
        qr[cr+1].pb({i,j});
//        cerr<< i<<' '<<j<<" c "<<a[i]<<' '<<b[i]<<'\n';
    }

    for2(i,k,1)
    {
//        cerr<< c[i].se<<'\n';
        Update(c[i].se);
        for(pii x: qr[i])
        {
            dd[x.fi]=Get(x.se+1,k)&1;
//            cerr<< x.fi<<' '<<dd[x.fi]<<'\n';
        }
//        cerr<<i<<'\n';
    }
//    return;
    int res=0;
    for1(i,1,n)
    {
        if (!dd[i]) res+=a[i];
        else res+=b[i];
    }
    cout << res;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("1017G.inp","r",stdin);
//    freopen("1017G.out","w",stdout);

    int t=1;//cin >> t;
    while (t--) {
        sol();
    }
}

/*
4 12
1 2 3
1 3
2 3
2 1
1 2
1 2
1 4
1 1
1 1
2 4
2 3
1 1
3 4



*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16828 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 3 ms 16720 KB Output is correct
4 Correct 3 ms 16720 KB Output is correct
5 Correct 3 ms 16888 KB Output is correct
6 Correct 3 ms 16720 KB Output is correct
7 Correct 3 ms 16816 KB Output is correct
8 Correct 4 ms 16720 KB Output is correct
9 Correct 3 ms 14692 KB Output is correct
10 Correct 3 ms 16720 KB Output is correct
11 Correct 3 ms 16720 KB Output is correct
12 Correct 3 ms 16720 KB Output is correct
13 Correct 3 ms 16736 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16828 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 3 ms 16720 KB Output is correct
4 Correct 3 ms 16720 KB Output is correct
5 Correct 3 ms 16888 KB Output is correct
6 Correct 3 ms 16720 KB Output is correct
7 Correct 3 ms 16816 KB Output is correct
8 Correct 4 ms 16720 KB Output is correct
9 Correct 3 ms 14692 KB Output is correct
10 Correct 3 ms 16720 KB Output is correct
11 Correct 3 ms 16720 KB Output is correct
12 Correct 3 ms 16720 KB Output is correct
13 Correct 3 ms 16736 KB Output is correct
14 Correct 9 ms 19272 KB Output is correct
15 Correct 16 ms 21584 KB Output is correct
16 Correct 21 ms 19948 KB Output is correct
17 Correct 29 ms 24144 KB Output is correct
18 Correct 30 ms 24140 KB Output is correct
19 Correct 27 ms 24136 KB Output is correct
20 Correct 32 ms 24144 KB Output is correct
21 Correct 26 ms 24056 KB Output is correct
22 Correct 21 ms 24144 KB Output is correct
23 Correct 21 ms 24140 KB Output is correct
24 Correct 21 ms 24052 KB Output is correct
25 Correct 20 ms 24140 KB Output is correct
26 Correct 23 ms 23888 KB Output is correct
27 Correct 37 ms 24148 KB Output is correct
28 Correct 39 ms 24144 KB Output is correct
29 Correct 30 ms 24144 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16828 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 3 ms 16720 KB Output is correct
4 Correct 3 ms 16720 KB Output is correct
5 Correct 3 ms 16888 KB Output is correct
6 Correct 3 ms 16720 KB Output is correct
7 Correct 3 ms 16816 KB Output is correct
8 Correct 4 ms 16720 KB Output is correct
9 Correct 3 ms 14692 KB Output is correct
10 Correct 3 ms 16720 KB Output is correct
11 Correct 3 ms 16720 KB Output is correct
12 Correct 3 ms 16720 KB Output is correct
13 Correct 3 ms 16736 KB Output is correct
14 Correct 9 ms 19272 KB Output is correct
15 Correct 16 ms 21584 KB Output is correct
16 Correct 21 ms 19948 KB Output is correct
17 Correct 29 ms 24144 KB Output is correct
18 Correct 30 ms 24140 KB Output is correct
19 Correct 27 ms 24136 KB Output is correct
20 Correct 32 ms 24144 KB Output is correct
21 Correct 26 ms 24056 KB Output is correct
22 Correct 21 ms 24144 KB Output is correct
23 Correct 21 ms 24140 KB Output is correct
24 Correct 21 ms 24052 KB Output is correct
25 Correct 20 ms 24140 KB Output is correct
26 Correct 23 ms 23888 KB Output is correct
27 Correct 37 ms 24148 KB Output is correct
28 Correct 39 ms 24144 KB Output is correct
29 Correct 30 ms 24144 KB Output is correct
30 Correct 78 ms 45896 KB Output is correct
31 Correct 82 ms 47176 KB Output is correct
32 Correct 112 ms 48356 KB Output is correct
33 Correct 204 ms 50760 KB Output is correct
34 Correct 66 ms 45640 KB Output is correct
35 Correct 157 ms 50912 KB Output is correct
36 Correct 183 ms 50816 KB Output is correct
37 Correct 193 ms 50760 KB Output is correct
38 Correct 154 ms 50760 KB Output is correct
39 Correct 161 ms 50772 KB Output is correct
40 Correct 119 ms 50504 KB Output is correct
41 Correct 154 ms 50760 KB Output is correct
42 Correct 182 ms 50760 KB Output is correct
43 Correct 81 ms 49448 KB Output is correct
44 Correct 80 ms 49476 KB Output is correct
45 Correct 79 ms 49676 KB Output is correct
46 Correct 103 ms 50756 KB Output is correct
47 Correct 105 ms 51016 KB Output is correct
48 Correct 151 ms 50760 KB Output is correct
49 Correct 116 ms 50760 KB Output is correct