Submission #1281440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281440		huyngodzz	Fire (BOI24_fire)	C++20	53 / 100	211 ms	18560 KiB

Main

///huynhocute123///
#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define pii pair<long long ,long long >
#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 = 8 * 1e5 + 999 ;
long long  n , m ;
pii shift[maxN];
vector<int> ar;
namespace sub1{
    bool check(){
        return (n <= 20);
    }
    struct sweep{
        long long  pos, kk;
        bool operator <(const sweep& rhs)const{
            if(pos != rhs.pos)return pos < rhs.pos;
            return kk < rhs.kk;
        }
    };
    vector<sweep>line;
    bool lmao(){
        sort(ALL(line));
//        for(auto [x , y] : line )cout << x << " " << y << '\n';
//        cout << '\n';
        int cnt =0 ;
        if(line[0].pos != 0)return 0;
        for(auto x : line){
            cnt += x.kk;

            if(cnt == 0)return 0;
        }
        return (cnt >= 1);
    }
    void solve(){
        int ans = MAX;
        FOR(mask , 1 , (1 << n) - 1){
            line.clear();
            FOR(i, 1, n){
                if( ((mask >> (i - 1)) & 1) == 1){
                    if(shift[i].F < shift[i].S){
                        line.pb({shift[i].F , 1});
                      if(shift[i].S + 1 <= m)line.pb({shift[i].S + 1 , -1});
                    }else{
                        line.pb({0  ,1});
                        line.pb({shift[i].S + 1 , -1});
                        line.pb({shift[i].F , 1});
                    }
                }
            }
//            cout << mask << '\n';
            if(lmao())minimize(ans, __builtin_popcount(mask));
        }
        cout << (ans == MAX ? -1 : ans);
    }
}
namespace sub2{
    long long  start = MAXLL, End;
    struct sweep{
        long long  pos, kk;
        bool operator <(const sweep& rhs)const{
            return pos < rhs.pos;
        }
    };
    vector<sweep>line;
    int mn[4 * maxN];
    int lazy[4 * maxN];

    void init(int id ,int l ,int r){
        mn[id] = MAX;
        lazy[id] =MAX;
        if(l == r)return;
        int mid = (l + r)/2;
        init(id << 1 , l ,mid);
        init(id<< 1 | 1, mid + 1, r);
    }
    void push(int id){
        if(lazy[id] >= MAX)return;
        minimize(lazy[id << 1] , lazy[id]);
        minimize(lazy[id << 1 | 1] , lazy[id]);
        minimize(mn[id << 1] , lazy[id]);
        minimize(mn[id << 1 | 1] , lazy[id]);
        lazy[id] = MAX;
    }
    void upd(int id ,int l ,int r, int u ,int v ,int val){
        if(v < l || u > r)return;
        if(u <= l && r <= v){
            minimize(mn[id] ,val);
            minimize(lazy[id] , val);
            return;
        }
        int mid = (l +r)/2;
        push(id);
        upd(id << 1 ,l ,mid ,u ,v, val);
        upd(id << 1 | 1,mid + 1, r, u ,v , val);
        minimize(mn[id], mn[id << 1 ]);
        minimize(mn[id], mn[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 mn[id];
        int mid = (l + r)/2;
        push(id);
        return min(get(id << 1 , l,mid ,u ,v ) , get(id << 1 | 1,mid + 1, r, u ,v));
    }
    void solve(){
        FOR(i, 1, n){
           if(shift[i].F > shift[i].S){
                shift[i].S += m;
           }else{
                shift[i].S += m;
                shift[i].F += m;
           }
           assert(shift[i].F < shift[i].S);
           minimizell(start , shift[i].F);
//           cout << shift[i].F << " " << shift[i].S << '\n';
        }
        End = start + m;
//        cerr << start << " "<< End << '\n';
        FOR(i, 1, n){
            line.pb({shift[i].F , i});
            ar.pb(shift[i].F);
            ar.pb(shift[i].S);
        }
        ar.pb(start);
        ar.pb(End);
        sort(ALL(line));
        sort(ALL(ar));
        ar.erase(unique(ALL(ar)),ar.end());
        int sz = ar.size()  + 2;
        init(1 , 1 , sz);
        int id = lower_bound(ALL(ar) , start) - ar.begin() + 1;
        upd(1, 1, sz, id, id,  0);
        for(auto [tick , id] : line){
            int r = shift[id].S;
            r = lower_bound(ALL(ar), shift[id].S) - ar.begin() + 1;
            int l = lower_bound(ALL(ar), shift[id].F) - ar.begin() + 1;
            int val = get(1, 1 , sz, l , sz);
            upd(1, 1, sz , l , r ,val + 1);
        }
        int pos = lower_bound(ALL(ar) , End) - ar.begin() + 1;
        int ans = get(1, 1, sz , pos, sz);
        cout << (ans > n ? -1 : ans);
        cerr << (ans > n ? -1 : ans);
//        cout << start << '\n';
    }
}
inline void solve(){
    cin >> n >> m ;
    FOR(i, 1, n){
        long long  u ,v;cin >> u >> v;
        shift[i] = {u ,v};
    }
//    if(sub1::check())return sub1::solve();
//    if(sub2::check())return sub2::solve();
    return sub2::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)

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

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26