Submission #846760

#	Time	Username	Problem	Language	Result	Execution time	Memory
846760		sugartheanh	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	781 ms	164136 KiB

fortune_telling2

#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];
vector<int>arr,post[N*3],st[(N*3)<<2];
void build(int id,int l,int r)
{
    if(l == r)
    {
        if(post[l].empty())
        {
            st[id].push_back(-1);
            return ;
        }
        for(auto u : post[l])
            st[id].push_back(u);
//        if(l == 11)
//        {
//            for(auto u : st[id])
//                cout<<u<<' ';
//            cout<<'\n';
//        }
        //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(st[id<<1].size() + st[id<<1|1].size());
    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)
    {
//        cout<<l<<' '<<r<<'\n';
//        for(auto u : st[id])
//            cout<<u<<' ';
//        cout<<'\n';
        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]].push_back(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;
}
//25
//24
//12
//19
//20
//8
//14
//15

Compilation message (stderr)

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

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65