Submission #1275228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275228		huyngodzz	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	390 ms	21440 KiB

fortune_telling2

///huynhocute123///
#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = b; i >= a; --i)
#define ALL(v) v.begin(),v.end()
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
//random_device rd;
//mt19937 rng(rd());
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
const int MAX = 1e9+9;
const long long  MAXLL = 1e18+9;
const double pi = 3.14159265358979323846;
const double rad = 3.14159265358979323846 /180;
bool minimize(int &u, int v){
    if(v < u){
        u = v;
        return 1;
    }
    return 0;
}
bool maximize(int &u, int v){
    if(v > u){
        u = v;
        return 1;
    }
    return 0;
}
bool maximizell(long long &u, long long v){
    if(v > u){
        u = v;
        return 1;
    }
    return 0;
}
bool minimizell(long long &u, long long v){
    if(v < u){
        u = v;
        return 1;
    }
    return 0;
}
const int  mod = 1e9 + 7;
inline int fastPow(int a, int n){
    if(n == 0) return 1;
    int t = fastPow(a, n >> 1);
    t = 1ll * t * t % mod;
    if(n & 1) t = 1ll * t * a % mod;
    return t;
}
inline void Add(int& x ,int y){
    x += y;
    if(x >= mod)x -=mod;
}
inline void Sub(int& x, int y){
    x-= y;
    if(x < 0)x += mod;
}
const int maxN = 4  * 1e5 + 99 ;
int n , k ;
int A[maxN][3], pos[maxN];
int lmao[maxN];
namespace sub1{
    bool check(){
        return (n <= 5000);
    }
    void solve(){
        FOR(j, 1, k){
            FOR(i, 1, n){
                if(A[i][pos[i]] <= lmao[j]){
                    pos[i] = 3 - pos[i];
                }
            }
        }
        long long ans = 0;
        FOR(i, 1, n)ans += A[i][pos[i]];
//        FOR(i, 1, n)cerr << pos[i] << " ";
        cout << ans;
    }
}
namespace sub3{
    bool check(){
        FOR(i, 2 ,k){
            if(lmao[i - 1] <= lmao[i])continue;
//            cout << lmao[i - 1] <<  " " << lmao[i] << '\n';
            cout << i << " "<<  123123 << '\n';
            return 0;
        }
        return 1;
    }
    int BIT[maxN * 4];
    int sz;
    void upd(int pos){
        for(; pos <= sz ; pos += (pos & -pos))BIT[pos]++;
    }
    int get(int pos){
        int sum =0;
        for(; pos >= 1 ; pos -= (pos & -pos))sum += BIT[pos];
        return sum;
    }
    int querry(int l ,int r){
        return get(r) - get(l - 1);
    }
    void solve(){
    long long ans = 0 ;
       vector<int> ar;
       FOR(i, 1, n){
            ar.pb(A[i][1]);
            ar.pb(A[i][2]);
            ar.pb(A[i][2] - 1);
       }
       FOR(i, 1, k)ar.pb(lmao[i]);
       sort(ALL(ar));
       ar.erase(unique(ALL(ar)), ar.end());
       sz = ar.size() + 1;
       FOR(i, 1, k){
            int pos = lower_bound(ALL(ar), lmao[i]) - ar.begin() + 1;
            upd(pos);
       }
       FOR(i, 1, n){
            if(A[i][1] >= A[i][2]){
                int l = lower_bound(ALL(ar), A[i][1]) - ar.begin() + 1;
                int x = querry(l ,sz);
                if((x% 2) == 1)pos[i] = 2;
            }else{
                int l = lower_bound(ALL(ar), A[i][1]) - ar.begin() + 1;
                int r = lower_bound(ALL(ar), A[i][2] - 1) - ar.begin() + 1;
                int x =  min(1,querry(l , r));
//                cout << x << " ";
                x += querry(r + 1, sz);
//                cout << x << '\n';
                if((x% 2) == 1)pos[i] = 2;


            }
       }
       FOR(i, 1, n)ans += A[i][pos[i]];
//       FOR(i, 1, n)cout << pos[i] << " " ;
      // 2 1 1 1 1
       cout << ans;


    }
}
namespace ac{
    int st[3 * 4 * maxN];
    void upd(int id ,int l ,int r,int pos ,int val){
        if(pos < l || pos > r)return;
        if(l  ==r){
            maximize(st[id] ,val);
            return;
        }
        int mid = (l + r)/2;
        upd(id << 1 , l , mid , pos ,val);
        upd(id << 1 | 1 ,mid + 1 ,r, pos ,val);
        st[id] = max(st[id << 1] , st[id << 1 | 1]);
    }
    int get(int id ,int l ,int r ,int u ,int v){
        if(v < l || u >r)return -MAX;
        if(u <= l && r <= v)return st[id];
        int mid = (l + r)/2;
        return max(get(id << 1 , l, mid ,u ,v) ,get(id << 1 | 1 ,mid + 1, r, u ,v));
    }
    int BIT[maxN * 4];
    int sz;
    void update(int pos){
        for(; pos <= sz ; pos += (pos & -pos))BIT[pos]++;
    }
    int get(int pos){
        int sum =0;
        for(; pos >= 1 ; pos -= (pos & -pos))sum += BIT[pos];
        return sum;
    }
    int querry(int l ,int r){
        assert(l <= r);
        return get(r) - get(l - 1);
    }
    vector<int> fpos[maxN];
    int sum[maxN];
    void solve(){
    vector<int> ar;
       FOR(i, 1, n){
            if(A[i][1] == A[i][2])ar.pb(A[i][1]);
            else if(A[i][1] < A[i][2]){
                ar.pb(A[i][1]);
                ar.pb(A[i][2]);
                ar.pb(A[i][2] - 1);
            }else{
                ar.pb(A[i][1]);
                ar.pb(A[i][2]);
                ar.pb(A[i][1] - 1);
            }
       }
       FOR(i, 1, k)ar.pb(lmao[i]);
       sort(ALL(ar));
       ar.erase(unique(ALL(ar)), ar.end());
       sz = ar.size() + 1;
       FOR(i, 1, k){
            int pos = lower_bound(ALL(ar), lmao[i]) - ar.begin() + 1;
            upd(1, 1, sz, pos, i);
       }
       FOR(i, 1, n){
            if(A[i][1] == A[i][2])continue;
            if(A[i][1] < A[i][2]){
                int l = lower_bound(ALL(ar), A[i][1]) - ar.begin() + 1;
                int r = lower_bound(ALL(ar), A[i][2] - 1) - ar.begin() + 1;
                int x = get(1, 1, sz, l ,r);
                if(1 <= x && x <= k){
                    sum[i] = 1;
                    fpos[x + 1].pb(i);
                }

            }else{
                int l = lower_bound(ALL(ar), A[i][2]) - ar.begin() + 1;
                int r = lower_bound(ALL(ar), A[i][1] - 1) - ar.begin() + 1;
                int x = get(1, 1, sz, l ,r);
                if(1 <= x && x <= k ){
                    sum[i] = 2;
                    fpos[x + 1].pb(i);
                }


            }
            if(sum[i] == 0){
                fpos[1].pb(i);
            }
       }
       REP(i , 1, k){
            int pos = lower_bound(ALL(ar), lmao[i]) - ar.begin() + 1;
            update(pos);
            for(auto id : fpos[i]){
                if(A[id][1] == A[id][2])continue;
                if(A[id][1] < A[id][2]){
                    int kk = lower_bound(ALL(ar), A[id][2]) - ar.begin() + 1;
                    sum[id] += querry(kk , sz);
                }else{
                    int kk = lower_bound(ALL(ar), A[id][1]) - ar.begin() + 1;
                    sum[id] += querry(kk , sz);

                }

            }

       }
       long long ans = 0;
       FOR(i, 1, n){
           int pos =( (sum[i] % 2) == 0 ? 1 : 2);
           if(A[i][1] == A[i][2])ans += A[i][1];
          else  ans += A[i][pos];
//            cout <<  ( (sum[i] % 2) == 0 ? 1 : 2) << " ";
//            cout << sum[i] << " ";

       }
       cout << ans;


    }

}
inline void solve(){
    cin >> n >>  k;
    FOR(i, 1, n){
        FOR(j, 1, 2)cin >> A[i][j];
        pos[i] = 1;
    }
    FOR(i, 1, k)cin >> lmao[i];
//    FOR(i, 1, k)cout << lmao[i] << '\n';
//    if(sub1::check())return sub1::solve();
//    if(sub3::check())return sub3::solve();
    ac::solve();
}
#define NAME "task"
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if(fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r" ,stdin);
        freopen(NAME".out", "w" ,stdout);
    }
    int tc = 1;
   // cin >> tc;
    while( tc-- )solve();
    cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ;


}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:286:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  286 |         freopen(NAME".inp", "r" ,stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:287:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  287 |         freopen(NAME".out", "w" ,stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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