Submission #1313079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313079		samarthkulkarni	Curtains (NOI23_curtains)	C++20	0 / 100	7 ms	496 KiB

curtains

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int N = 5e5+10;
vector<int> st[N];
vector<pair<int,int>> qw[N];
int mx[N<<2], mn[N<<2];
int lzy[N<<2];
int seg_n;

// Completely inline everything - no function calls
inline void solve() {
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);  // scanf is faster than cin for large input
    
    seg_n = n + 2;
    memset(mx, -1, sizeof(int) * (seg_n << 2));
    memset(mn, -1, sizeof(int) * (seg_n << 2));
    
    for (int i = 0; i < m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        st[r].push_back(l);
    }
    
    for (int i = 0; i < q; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        qw[r].push_back({l, i});
    }
    
    for (int i = 1; i <= n; i++) {
        sort(st[i].begin(), st[i].end(), greater<int>());
        sort(qw[i].begin(), qw[i].end(), greater<pair<int,int>>());
    }
    
    vector<int> res(q);
    
    for (int i = 1; i <= n; i++) {
        int j = 0;
        int st_sz = st[i].size();
        
        for (auto& [ql, e] : qw[i]) {
            while (j < st_sz && st[i][j] >= ql) {
                int pos = st[i][j];
                
                // Inline point update
                {
                    int id = 1, l = 0, r = seg_n - 1;
                    static int path[20];
                    int path_len = 0;
                    
                    while (l < r) {
                        if (lzy[id]) {
                            mx[id] = mn[id] = lzy[id];
                            lzy[id<<1] = lzy[id];
                            lzy[id<<1|1] = lzy[id];
                            lzy[id] = 0;
                        }
                        path[path_len++] = id;
                        int mid = (l + r) >> 1;
                        if (pos <= mid) { id = id<<1; r = mid; }
                        else { id = id<<1|1; l = mid+1; }
                    }
                    if (lzy[id]) { mx[id] = mn[id] = lzy[id]; lzy[id] = 0; }
                    mx[id] = mn[id] = i;
                    
                    while (path_len--) {
                        id = path[path_len];
                        int left = id<<1, right = id<<1|1;
                        int lmx = lzy[left] ? lzy[left] : mx[left];
                        int lmn = lzy[left] ? lzy[left] : mn[left];
                        int rmx = lzy[right] ? lzy[right] : mx[right];
                        int rmn = lzy[right] ? lzy[right] : mn[right];
                        mx[id] = max(lmx, rmx);
                        mn[id] = min(lmn, rmn);
                    }
                }
                
                // Inline range update (only if pos > 1)
                if (pos > 1) {
                    static int stk[40];
                    int top = 0;
                    stk[top++] = 1;
                    stk[top++] = 0;
                    stk[top++] = seg_n - 1;
                    
                    while (top) {
                        int r = stk[--top];
                        int l = stk[--top];
                        int id = stk[--top];
                        
                        if (lzy[id]) {
                            mx[id] = mn[id] = lzy[id];
                            if (l != r) {
                                lzy[id<<1] = lzy[id];
                                lzy[id<<1|1] = lzy[id];
                            }
                            lzy[id] = 0;
                        }
                        
                        if (mx[id] < pos - 1 || 1 > r || pos - 1 < l) continue;
                        
                        if (1 <= l && pos - 1 >= r && mn[id] >= pos - 1) {
                            mx[id] = mn[id] = i;
                            if (l != r) {
                                lzy[id<<1] = i;
                                lzy[id<<1|1] = i;
                            }
                            continue;
                        }
                        
                        if (l == r) continue;
                        
                        int mid = (l + r) >> 1;
                        
                        // Push to stack in reverse order
                        if (pos - 1 > mid) {
                            int rmx = lzy[id<<1|1] ? lzy[id<<1|1] : mx[id<<1|1];
                            if (rmx >= pos - 1) {
                                stk[top++] = id<<1|1;
                                stk[top++] = mid + 1;
                                stk[top++] = r;
                            }
                        }
                        if (1 <= mid) {
                            int lmx = lzy[id<<1] ? lzy[id<<1] : mx[id<<1];
                            if (lmx >= pos - 1) {
                                stk[top++] = id<<1;
                                stk[top++] = l;
                                stk[top++] = mid;
                            }
                        }
                        
                        // Update current node after children will be processed
                        int left = id<<1, right = id<<1|1;
                        int lmx = lzy[left] ? lzy[left] : mx[left];
                        int lmn = lzy[left] ? lzy[left] : mn[left];
                        int rmx = lzy[right] ? lzy[right] : mx[right];
                        int rmn = lzy[right] ? lzy[right] : mn[right];
                        mx[id] = max(lmx, rmx);
                        mn[id] = min(lmn, rmn);
                    }
                }
                j++;
            }
            
            // Inline query
            {
                int id = 1, l = 0, r = seg_n - 1;
                while (l < r) {
                    if (lzy[id]) {
                        mx[id] = mn[id] = lzy[id];
                        lzy[id<<1] = lzy[id];
                        lzy[id<<1|1] = lzy[id];
                        lzy[id] = 0;
                    }
                    int mid = (l + r) >> 1;
                    if (ql <= mid) { id = id<<1; r = mid; }
                    else { id = id<<1|1; l = mid+1; }
                }
                res[e] = ((lzy[id] ? lzy[id] : mx[id]) == i);
            }
        }
        
        // Process remaining curtains
        while (j < st_sz) {
            int pos = st[i][j];
            
            // Same point update as above
            {
                int id = 1, l = 0, r = seg_n - 1;
                static int path[20];
                int path_len = 0;
                
                while (l < r) {
                    if (lzy[id]) {
                        mx[id] = mn[id] = lzy[id];
                        lzy[id<<1] = lzy[id];
                        lzy[id<<1|1] = lzy[id];
                        lzy[id] = 0;
                    }
                    path[path_len++] = id;
                    int mid = (l + r) >> 1;
                    if (pos <= mid) { id = id<<1; r = mid; }
                    else { id = id<<1|1; l = mid+1; }
                }
                if (lzy[id]) { mx[id] = mn[id] = lzy[id]; lzy[id] = 0; }
                mx[id] = mn[id] = i;
                
                while (path_len--) {
                    id = path[path_len];
                    int left = id<<1, right = id<<1|1;
                    int lmx = lzy[left] ? lzy[left] : mx[left];
                    int lmn = lzy[left] ? lzy[left] : mn[left];
                    int rmx = lzy[right] ? lzy[right] : mx[right];
                    int rmn = lzy[right] ? lzy[right] : mn[right];
                    mx[id] = max(lmx, rmx);
                    mn[id] = min(lmn, rmn);
                }
            }
            
            // Same range update
            if (pos > 1) {
                static int stk[40];
                int top = 0;
                stk[top++] = 1;
                stk[top++] = 0;
                stk[top++] = seg_n - 1;
                
                while (top) {
                    int r = stk[--top];
                    int l = stk[--top];
                    int id = stk[--top];
                    
                    if (lzy[id]) {
                        mx[id] = mn[id] = lzy[id];
                        if (l != r) {
                            lzy[id<<1] = lzy[id];
                            lzy[id<<1|1] = lzy[id];
                        }
                        lzy[id] = 0;
                    }
                    
                    if (mx[id] < pos - 1 || 1 > r || pos - 1 < l) continue;
                    
                    if (1 <= l && pos - 1 >= r && mn[id] >= pos - 1) {
                        mx[id] = mn[id] = i;
                        if (l != r) {
                            lzy[id<<1] = i;
                            lzy[id<<1|1] = i;
                        }
                        continue;
                    }
                    
                    if (l == r) continue;
                    
                    int mid = (l + r) >> 1;
                    
                    if (pos - 1 > mid) {
                        int rmx = lzy[id<<1|1] ? lzy[id<<1|1] : mx[id<<1|1];
                        if (rmx >= pos - 1) {
                            stk[top++] = id<<1|1;
                            stk[top++] = mid + 1;
                            stk[top++] = r;
                        }
                    }
                    if (1 <= mid) {
                        int lmx = lzy[id<<1] ? lzy[id<<1] : mx[id<<1];
                        if (lmx >= pos - 1) {
                            stk[top++] = id<<1;
                            stk[top++] = l;
                            stk[top++] = mid;
                        }
                    }
                    
                    int left = id<<1, right = id<<1|1;
                    int lmx = lzy[left] ? lzy[left] : mx[left];
                    int lmn = lzy[left] ? lzy[left] : mn[left];
                    int rmx = lzy[right] ? lzy[right] : mx[right];
                    int rmn = lzy[right] ? lzy[right] : mn[right];
                    mx[id] = max(lmx, rmx);
                    mn[id] = min(lmn, rmn);
                }
            }
            j++;
        }
    }
    
    for (int i = 0; i < q; i++) {
        puts(res[i] ? "YES" : "NO");  // puts is faster than cout
    }
}

int main() {
    solve();
    return 0;
}

Compilation message (stderr)

curtains.cpp: In function 'void solve()':
curtains.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d%d%d", &n, &m, &q);  // scanf is faster than cin for large input
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf("%d%d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~
curtains.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d%d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~

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