oj.uz

Submission #846746

# Submission time Handle Problem Language Result Execution time Memory
846746 2023-09-08T11:15:58 Z sugartheanh Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 72 ms 70860 KB 
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define fi first
#define se second
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define ii pair<int,int>
#define task "new"
#define ll long long
using namespace std;
const int mod=1e9+7;
const int N=2e5+5;
int n,k,a[N],b[N],t[N];
int post[N*3];
vector<int>arr,st[(N*3)<<2];
void build(int id,int l,int r)
{
    if(l == r)
    {
        st[id].push_back(post[l] > 0 ? post[l] : -1);
        return ;
    }
    int mid = l + r >> 1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    st[id].resize(r-l+1);
    merge(st[id<<1].begin(), st[id<<1].end(),
          st[id<<1|1].begin(), st[id<<1|1].end(), st[id].begin());
}
int getmax(int id,int l,int r,int u,int v)
{
    if(r < u || v < l)
        return 0;
    if(u <= l && r <= v)
    {
        return st[id].back();
    }
    int mid = l + r >> 1;
    return max(getmax(id<<1,l,mid,u,v), getmax(id<<1|1,mid+1,r,u,v));
}
int getnum(int id,int l,int r,int u,int v,int k)
{
    if(r < u || v < l)
        return 0;
    if(u <= l && r <= v)
    {
        int res = lower_bound(st[id].begin(),st[id].end(),k) - st[id].begin();
        return st[id].size() - res;
    }
    int mid = l + r >> 1;
    return getnum(id<<1,l,mid,u,v,k) + getnum(id<<1|1,mid+1,r,u,v,k);
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin>>n>>k;
    fo(i,1,n)
    {
        cin>>a[i]>>b[i];
        arr.push_back(a[i]);
        arr.push_back(b[i]);
    }
    fo(i,1,k)
    {
        cin>>t[i];
        arr.push_back(t[i]);
    }
    sort(arr.begin(),arr.end());
    int m = arr.size();
    fo(i,1,n)
    {
        a[i] = upper_bound(arr.begin(),arr.end(),a[i]) - arr.begin();
        b[i] = upper_bound(arr.begin(),arr.end(),b[i]) - arr.begin();
    }
    fo(i,1,k)
    {
        t[i] = upper_bound(arr.begin(),arr.end(),t[i]) - arr.begin();
        post[t[i]] = i;
    }
    build(1,1,m);
    ll ans = 0;
    fo(i,1,n)
    {
        bool sw = 0;
        if(a[i] > b[i])
            swap(a[i], b[i]), sw = 1;
        int pos = getmax(1,1,m,a[i],b[i]-1);
        int num = getnum(1,1,m,b[i],m,pos);
        if(pos > 0)
        {
            ans += arr[num & 1 ? a[i]-1 : b[i]-1];
            //cout<<arr[num & 1 ? a[i]-1 : b[i]-1]<<'\n';
        }
        else
        {
            ans += arr[(num + sw) & 1 ? b[i]-1 : a[i]-1];
            //cout<<arr[(num + sw) & 1 ? b[i]-1 : a[i]-1]<<'\n';
        }
    }
    cout<<ans;
}

Compilation message

fortune_telling2.cpp: In function 'void build(int, int, int)':
fortune_telling2.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     int mid = l + r >> 1;
      |               ~~^~~
fortune_telling2.cpp: In function 'int getmax(int, int, int, int, int)':
fortune_telling2.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = l + r >> 1;
      |               ~~^~~
fortune_telling2.cpp: In function 'int getnum(int, int, int, int, int, int)':
fortune_telling2.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = l + r >> 1;
      |               ~~^~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 60248 KB Output is correct
2 Correct 13 ms 60248 KB Output is correct
3 Correct 14 ms 60248 KB Output is correct
4 Correct 13 ms 60248 KB Output is correct
5 Correct 14 ms 60248 KB Output is correct
6 Correct 14 ms 60456 KB Output is correct
7 Correct 14 ms 60248 KB Output is correct
8 Correct 14 ms 60248 KB Output is correct
9 Correct 14 ms 60248 KB Output is correct
10 Correct 13 ms 60460 KB Output is correct
11 Correct 13 ms 60460 KB Output is correct
12 Correct 14 ms 60248 KB Output is correct
13 Correct 14 ms 60248 KB Output is correct
14 Correct 29 ms 63576 KB Output is correct
15 Correct 49 ms 67036 KB Output is correct
16 Incorrect 72 ms 70860 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 60248 KB Output is correct
2 Correct 13 ms 60248 KB Output is correct
3 Correct 14 ms 60248 KB Output is correct
4 Correct 13 ms 60248 KB Output is correct
5 Correct 14 ms 60248 KB Output is correct
6 Correct 14 ms 60456 KB Output is correct
7 Correct 14 ms 60248 KB Output is correct
8 Correct 14 ms 60248 KB Output is correct
9 Correct 14 ms 60248 KB Output is correct
10 Correct 13 ms 60460 KB Output is correct
11 Correct 13 ms 60460 KB Output is correct
12 Correct 14 ms 60248 KB Output is correct
13 Correct 14 ms 60248 KB Output is correct
14 Correct 29 ms 63576 KB Output is correct
15 Correct 49 ms 67036 KB Output is correct
16 Incorrect 72 ms 70860 KB Output isn't correct
17 Halted 0 ms 0 KB -