Submission #1169690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169690		Thanhs	Curtains (NOI23_curtains)	C++20	100 / 100	686 ms	68908 KiB

curtains

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

#define name "TENBAI"
#define fi first
#define se second
#define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 5e5 + 5;

int n, m, q, ans[NM];
vector<array<int, 4>> Q;

struct node
{
    int L = 0, R = 0;
    node() {}
    node(int _L, int _R) : L(_L), R(_R) {}
    node operator+(const node& o)
    {
        if (!L)
            return o;
        if (!o.L)
            return *this;
        return (R < o.L - 1 ? o : node(L, max(R, o.R)));
    }
}dt[4 * NM];

void upd(int l, int r, int x = 1, int lx = 1, int rx = n)
{
    if (lx == rx)
    {
        dt[x] = node(l, r);
        return;
    }
    int m = lx + rx >> 1;
    if (m >= l)
        upd(l, r, x << 1, lx, m);
    else
        upd(l, r, x << 1 | 1, m + 1, rx);
    dt[x] = dt[x << 1] + dt[x << 1 | 1];
}

node get(int l, int r, int x = 1, int lx = 1, int rx = n)
{
    if (l > rx || lx > r)
        return node();
    if (lx >= l && rx <= r)
        return dt[x];
    int m = lx + rx >> 1;
    return get(l, r, x << 1, lx, m) + get(l, r, x << 1 | 1, m + 1, rx);
}

void solve()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        Q.push_back({r, 0, l, 0});
    }
    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        Q.push_back({r, 1, l, i});
    }
    sort(Q.begin(), Q.end());
    for (auto t : Q)
    {
        if (!t[1])
            upd(t[2], t[0]);
        else
        {
            auto nd = get(t[2], t[0]);
            ans[t[3]] = (nd.L == t[2] && nd.R == t[0]);
        }
    }
    for (int i = 1; i <= q; i++)
        cout << (ans[i] ? "YES" : "NO") << endl;
}

signed main()
{
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    else if (fopen(name".inp", "r"))
    {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int tc = 1; 
    // cin >> tc;
    while (tc--)
        solve();
}

Compilation message (stderr)

curtains.cpp: In function 'int main()':
curtains.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         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