Submission #1124402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124402		SoMotThanhXuan	Curtains (NOI23_curtains)	C++20	100 / 100	906 ms	74740 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define mp make_pair
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
const int mod = 1e9 + 7;
inline bool maximize(int &u, int v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
inline bool minimize(int &u, int v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
inline bool maximizell(long long &u, long long v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
inline bool minimizell(long long &u, long long v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
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 &u, int v){
    u += v;
    if(u >= mod) u -= mod;
}
inline void sub(int &u, int v){
    u -= v;
    if(u < 0) u += mod;
}
const int maxN = 5e5 + 5;
int n, m, l[maxN], r[maxN], q, s[maxN], e[maxN];
namespace subtask1{
    bool check(){
        return max(n, max(m, q)) <= 2000;
    }
    bitset<2001> f[2001];
    vector<int> adj[2001];
    void solve(){
        FOR(i, 1, m){
            adj[l[i]].emplace_back(r[i]);
        }
        REP(i, n, 1){
            for(int r : adj[i]){
                f[i].set(r);
                FOR(x, i + 1, r + 1)f[i] |=  f[x], f[i];
            }
        }
        FOR(i, 1, q){
            if(f[s[i]][e[i]])cout << "YES\n";
            else cout << "NO\n";
        }
    }
}
namespace ac{
    struct Interval{
        vector<int> it, lz;
        Interval(int _n = 0, int v = 0){
            n = _n;
            it.resize(n << 2, v);
            lz.resize(n << 2, v);
        }
        void push(int id){
            int &z = lz[id];
            if(z == 0) return;
            maximize(lz[id << 1], z);
            maximize(lz[id << 1 | 1], z);
            maximize(it[id << 1], z);
            maximize(it[id << 1 | 1], z);
            z = 0;
            return;
        }
        void modify(int id, int l, int r, int u, int v, int val){
            if(l > v || r < u)return;
            if(l >= u && r <= v){
                maximize(it[id], val);
                maximize(lz[id], val);
                return;
            }
            int mid = l + r >> 1;
            push(id);
            modify(id << 1, l, mid, u, v, val);
            modify(id << 1 | 1, mid + 1, r, u, v, val);
            it[id] = min(it[id << 1], it[id << 1 | 1]);
        }
        int get(int id, int l, int r, int u, int v){
            if(l >= u && r <= v) return it[id];
            int mid = l + r >> 1;
            push(id);
            if(v <= mid) return get(id << 1, l, mid, u, v);
            if(u > mid) return get(id << 1 | 1, mid + 1, r, u, v);
            return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
        }
    };
    vector<int> start[maxN];
    vector<int> query[maxN];
    bool answer[maxN];
    void solve(){
        Interval tree = Interval(n, 0);
        FOR(i, 1, m){
            start[r[i]].emplace_back(l[i]);
        }
        FOR(i, 1, q){
            query[e[i]].emplace_back(i);
        }
        FOR(r, 1, n){
            for(int l : start[r])tree.modify(1, 1, n, l, r, l);
            for(int id : query[r]){
                answer[id] = tree.get(1, 1, n, s[id], r) >= s[id];
            }
        }
        FOR(id, 1, q)cout << (answer[id] ? "YES" : "NO") << "\n";
    }
}
void process(){
    cin >> n >> m >> q;
    FOR(i, 1, m){
        cin >> l[i] >> r[i];
    }
    FOR(i, 1, q){
        cin >> s[i] >> e[i];
    }
//    if(subtask1 :: check()) return subtask1 :: solve();
    return ac :: solve();
}
#define NAME "Curtains"
int main(){
    if(fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
//    cin >> t;
    while(t--)
        process();
    cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ;
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20