oj.uz

Submission #1100893

# Submission time Handle Problem Language Result Execution time Memory
1100893 2024-10-15T02:03:53 Z lampooppp Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 197 ms 45804 KB 
#include <bits/stdc++.h>
using namespace std;

const int N=2e5;

int st[4*N+1],n,q;

void update(int x, int low, int hi ,int i, int k)
{
    if(low==hi) {st[x]=max(st[x],k); return;}
    int mid = low+hi>>1;
    if(i<=mid) update(x*2,low,mid,i,k);
    else update(x*2+1,mid+1,hi,i,k);
    st[x]=max(st[x*2],st[x*2+1]);
}

int getmx(int x, int low ,int hi, int i, int j)
{
    if(low>hi || low >j || hi < i) return 0;
    if(low>=i && hi<=j) return st[x];
    int mid=low+hi>>1;
    return max(getmx(x*2,low,mid,i,j), getmx(x*2+1,mid+1,hi,i,j));
}

int bit[3*N+100];

void add(int x)
{
    for(; x<=2*n+q+1;x+=x&(-x))
    {
        bit[x]++;
    }
}

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

int a[N+1],b[N+1],t[N+1];
int ag[N+1],bg[N+1];
int last[N+1];
int id[N+1];
map<int,int> mp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for(int i=1;i<=n;++i)
    {
        cin >> a[i] >> b[i];
        ag[i]=a[i];
        bg[i]=b[i];
        mp[a[i]]=0;
        mp[b[i]]=0;
    }
    for(int i=1;i<=q;++i)
    {
        cin >> t[i];
        mp[t[i]]=0;
    }
    int z=0;
    for(auto & k : mp) k.second = ++z;
    for(int i=1;i<=q;++i)
    {
        t[i] = mp[t[i]];
        update(1,1,2*n+q,t[i],i);
       // cout << t[i] << '\n';
    }
    for(int i=1;i<=n;++i)
    {
        a[i]=mp[a[i]];
        b[i]=mp[b[i]];
        last[i]=getmx(1,1,2*n+q,min(a[i],b[i]),max(a[i],b[i])-1);
      //  cout << a[i] << " " << b[i] << '\n';
        //cout << last[i] << " ";
        id[i]=i;
    }
   // cout << '\n';
    sort(id+1,id+n+1,[] (int x, int y)
         {
             return last[x]>last[y];
         });
   // cout << "WTF";
    long long ans=0;
    int now=q;
    for(int i=1;i<=n;++i)
    {
        int j = id[i];
       // cout << j << " " << last[j] << '\n';
        while(now > 0 && now>=last[j])
        {
            add(t[now]);
           // cout << "ADD : " << t[now] << '\n';
            now--;
        }
       // cout << "GET : " << max(a[j],b[j]) << '\n';
        int k = get(2*n+q+1) - get(max(a[j],b[j])-1);
       // cout << k << '\n';
        int cc=0;
        if(a[j]>b[j])
        {
            swap(a[j],b[j]);
            swap(ag[j],bg[j]);
            cc=1;
        }
        if(last[j]>0) cc=1;
        k%=2;
        cc^=k;
        if(cc) ans+=(long long)bg[j];
        else ans+=(long long)ag[j];
    }
    cout << ans;
}

Compilation message

fortune_telling2.cpp: In function 'void update(int, int, int, int, int)':
fortune_telling2.cpp:11:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |     int mid = low+hi>>1;
      |               ~~~^~~
fortune_telling2.cpp: In function 'int getmx(int, int, int, int, int)':
fortune_telling2.cpp:21:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int mid=low+hi>>1;
      |             ~~~^~~

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 8528 KB Output is correct
3 Correct 3 ms 8784 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 3 ms 8784 KB Output is correct
7 Correct 3 ms 8784 KB Output is correct
8 Correct 3 ms 8784 KB Output is correct
9 Correct 2 ms 8784 KB Output is correct
10 Correct 2 ms 8528 KB Output is correct
11 Correct 3 ms 8784 KB Output is correct
12 Correct 2 ms 8528 KB Output is correct
13 Correct 3 ms 8528 KB Output is correct
14 Correct 19 ms 10088 KB Output is correct
15 Correct 39 ms 11344 KB Output is correct
16 Correct 64 ms 13380 KB Output is correct
17 Correct 89 ms 14720 KB Output is correct
18 Correct 89 ms 14700 KB Output is correct
19 Correct 88 ms 14920 KB Output is correct
20 Correct 93 ms 14920 KB Output is correct
21 Correct 84 ms 14920 KB Output is correct
22 Correct 61 ms 12872 KB Output is correct
23 Correct 50 ms 11860 KB Output is correct
24 Correct 48 ms 11080 KB Output is correct
25 Correct 63 ms 13392 KB Output is correct
26 Correct 53 ms 12368 KB Output is correct
27 Correct 63 ms 12872 KB Output is correct
28 Correct 58 ms 12872 KB Output is correct
29 Correct 78 ms 13908 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 2 ms 8528 KB Output is correct
3 Correct 3 ms 8784 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 3 ms 8784 KB Output is correct
7 Correct 3 ms 8784 KB Output is correct
8 Correct 3 ms 8784 KB Output is correct
9 Correct 2 ms 8784 KB Output is correct
10 Correct 2 ms 8528 KB Output is correct
11 Correct 3 ms 8784 KB Output is correct
12 Correct 2 ms 8528 KB Output is correct
13 Correct 3 ms 8528 KB Output is correct
14 Correct 19 ms 10088 KB Output is correct
15 Correct 39 ms 11344 KB Output is correct
16 Correct 64 ms 13380 KB Output is correct
17 Correct 89 ms 14720 KB Output is correct
18 Correct 89 ms 14700 KB Output is correct
19 Correct 88 ms 14920 KB Output is correct
20 Correct 93 ms 14920 KB Output is correct
21 Correct 84 ms 14920 KB Output is correct
22 Correct 61 ms 12872 KB Output is correct
23 Correct 50 ms 11860 KB Output is correct
24 Correct 48 ms 11080 KB Output is correct
25 Correct 63 ms 13392 KB Output is correct
26 Correct 53 ms 12368 KB Output is correct
27 Correct 63 ms 12872 KB Output is correct
28 Correct 58 ms 12872 KB Output is correct
29 Correct 78 ms 13908 KB Output is correct
30 Correct 197 ms 20296 KB Output is correct
31 Runtime error 166 ms 45804 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -