oj.uz

Submission #1100982

# Submission time Handle Problem Language Result Execution time Memory
1100982 2024-10-15T07:15:23 Z proplayer Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 264 ms 29992 KB 
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
const int maxN = 2e5 + 5;
const int LG = 19;
int a[maxN],b[maxN],t[maxN];
int sp[LG][maxN];
int lg[maxN],id[maxN];
lli cnt[maxN],bit[maxN];
lli res;
int n,k;
vector<int> v;
vector<pair<int,int>> q;
void presp()
{
    lg[1] = 0;
    for (int i = 1;i <= k;++i) sp[0][i] = id[i];
    for (int i = 2;i <= k;++i) lg[i] = lg[i / 2] + 1;
    for (int j = 1;j < LG;++j)
        for (int i = 1;i <= k - (1 << j) + 1;++i)
        sp[j][i] = max(sp[j - 1][i],sp[j - 1][i + (1 << (j - 1))]);
}
int get(int l,int r)
{
    int k = lg[r - l + 1];
    return max(sp[k][l],sp[k][r - (1 << k) + 1]);
}
bool cmp(int x,int y)
{
    if (t[x] == t[y]) return x > y;
    return t[x] < t[y];
}
void input()
{
    cin >> n >> k;
    for (int i = 1;i <= n;++i)
    {
        cin >> a[i] >> b[i];
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    for (int i = 1;i <= k;++i)
    {
        id[i] = i;
        cin >> t[i];
        v.push_back(t[i]);
    }
    sort(id + 1,id + k + 1,cmp);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    presp();
}
int getid(int x)
{
    return lower_bound(v.begin(),v.end(),x) + 1 - v.begin();
}
bool cmp1(pair<int,int> x,pair<int,int> y)
{
    return max(a[x.second],b[x.second]) > max(b[y.second],a[y.second]);
}
void update(int i,int val)
{
    while (i <= k)
    {
        bit[i] += val;
        i += (i & (-i));
    }
}
lli getsum(int l,int r)
{
    --l;
    lli res = 0;
    while (l > 0)
    {
        res -= bit[l];
        l -= (l & (-l));
    }
    while (r > 0)
    {
        res += bit[r];
        r -= (r & (-r));
    }
    return res;
}
void solve()
{
    for (int i = 1;i <= n;++i)
    {
        int mn = min(a[i],b[i]);
        int mx = max(a[i],b[i]);
        int l = 1,r = k,id1 = 0,id2 = 0;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (t[id[mid]] >= mn)
            {
                id1 = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        l = 1;r = k;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (t[id[mid]] < mx)
            {
                id2 = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        //cerr << get(id1,id2) << " " << b[i] << " " << id1 << " "  << id2 << "\n";
        if (id1 > id2 || id1 == 0 || id2 == 0) q.push_back({0,i});
        else q.push_back({get(id1,id2),i});
    }
    sort(q.begin(),q.end(),cmp1);
    int it = k;
    lli ans = 0;
    for (int i = 0;i < q.size();++i)
    {
        while (t[id[it]] >= max(b[q[i].second],a[q[i].second]) && it >= 1)
        {
            //cerr << max(b[q[i].second],a[q[i].second]) << " " << id[it] << " " << t[id[it]] << " "  << i << "\n";
            update(id[it],1);--it;
        }
        //cerr << getsum(q[i].first + 1,k) << "\n";
        //cout << q[i].first + 1 << " " << k << "A\n";
        res = getsum(q[i].first + 1,k);
        //cout << q[i].first <<  "\n";
        if (q[i].first == 0 && b[q[i].second] > a[q[i].second]) res--;
        //cout << res << "\n";
        if (res % 2 == 0) ans += max(b[q[i].second],a[q[i].second]);
        else ans += min(b[q[i].second],a[q[i].second]);
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("P1.inp","r",stdin);
    //freopen("P1.out","w",stdout);
    input();
    solve();
}

Compilation message

fortune_telling2.cpp: In function 'void solve()':
fortune_telling2.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0;i < q.size();++i)
      |                    ~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 2 ms 12624 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 3 ms 12624 KB Output is correct
5 Correct 2 ms 12816 KB Output is correct
6 Correct 3 ms 12624 KB Output is correct
7 Correct 2 ms 12624 KB Output is correct
8 Correct 3 ms 12624 KB Output is correct
9 Correct 2 ms 12624 KB Output is correct
10 Correct 2 ms 12624 KB Output is correct
11 Correct 3 ms 12624 KB Output is correct
12 Correct 3 ms 12624 KB Output is correct
13 Correct 3 ms 12624 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 2 ms 12624 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 3 ms 12624 KB Output is correct
5 Correct 2 ms 12816 KB Output is correct
6 Correct 3 ms 12624 KB Output is correct
7 Correct 2 ms 12624 KB Output is correct
8 Correct 3 ms 12624 KB Output is correct
9 Correct 2 ms 12624 KB Output is correct
10 Correct 2 ms 12624 KB Output is correct
11 Correct 3 ms 12624 KB Output is correct
12 Correct 3 ms 12624 KB Output is correct
13 Correct 3 ms 12624 KB Output is correct
14 Correct 10 ms 17168 KB Output is correct
15 Correct 27 ms 17488 KB Output is correct
16 Correct 40 ms 17876 KB Output is correct
17 Correct 40 ms 18252 KB Output is correct
18 Correct 40 ms 18252 KB Output is correct
19 Correct 38 ms 18280 KB Output is correct
20 Correct 44 ms 18252 KB Output is correct
21 Correct 37 ms 18280 KB Output is correct
22 Correct 26 ms 20008 KB Output is correct
23 Correct 27 ms 18252 KB Output is correct
24 Correct 29 ms 20052 KB Output is correct
25 Correct 26 ms 20044 KB Output is correct
26 Correct 31 ms 20052 KB Output is correct
27 Correct 36 ms 20044 KB Output is correct
28 Correct 35 ms 20152 KB Output is correct
29 Correct 42 ms 18204 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 2 ms 12624 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 3 ms 12624 KB Output is correct
5 Correct 2 ms 12816 KB Output is correct
6 Correct 3 ms 12624 KB Output is correct
7 Correct 2 ms 12624 KB Output is correct
8 Correct 3 ms 12624 KB Output is correct
9 Correct 2 ms 12624 KB Output is correct
10 Correct 2 ms 12624 KB Output is correct
11 Correct 3 ms 12624 KB Output is correct
12 Correct 3 ms 12624 KB Output is correct
13 Correct 3 ms 12624 KB Output is correct
14 Correct 10 ms 17168 KB Output is correct
15 Correct 27 ms 17488 KB Output is correct
16 Correct 40 ms 17876 KB Output is correct
17 Correct 40 ms 18252 KB Output is correct
18 Correct 40 ms 18252 KB Output is correct
19 Correct 38 ms 18280 KB Output is correct
20 Correct 44 ms 18252 KB Output is correct
21 Correct 37 ms 18280 KB Output is correct
22 Correct 26 ms 20008 KB Output is correct
23 Correct 27 ms 18252 KB Output is correct
24 Correct 29 ms 20052 KB Output is correct
25 Correct 26 ms 20044 KB Output is correct
26 Correct 31 ms 20052 KB Output is correct
27 Correct 36 ms 20044 KB Output is correct
28 Correct 35 ms 20152 KB Output is correct
29 Correct 42 ms 18204 KB Output is correct
30 Correct 70 ms 22104 KB Output is correct
31 Correct 100 ms 24256 KB Output is correct
32 Correct 147 ms 24604 KB Output is correct
33 Correct 246 ms 29880 KB Output is correct
34 Correct 55 ms 21956 KB Output is correct
35 Correct 246 ms 29888 KB Output is correct
36 Correct 232 ms 29884 KB Output is correct
37 Correct 264 ms 29880 KB Output is correct
38 Correct 254 ms 29876 KB Output is correct
39 Correct 229 ms 29368 KB Output is correct
40 Correct 194 ms 29368 KB Output is correct
41 Correct 220 ms 29984 KB Output is correct
42 Correct 222 ms 29884 KB Output is correct
43 Correct 143 ms 28176 KB Output is correct
44 Correct 116 ms 28344 KB Output is correct
45 Correct 113 ms 28868 KB Output is correct
46 Correct 126 ms 29884 KB Output is correct
47 Correct 136 ms 29992 KB Output is correct
48 Correct 180 ms 29880 KB Output is correct
49 Correct 171 ms 29984 KB Output is correct