Submission #1094582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094582		cpptowin	Segments (IZhO18_segments)	C++17	100 / 100	3531 ms	26168 KiB

segments

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 1050;
const int mod = 1e9 + 7;
vector<array<int, 3>> range, qry;
vi l[N], r[N];
vii a[N];
int len[N];
int cnt;
void build()
{
    sort(all(range), [](array<int, 3> a, array<int, 3> b)
         {
        if(a[1] - a[0] == b[1] - b[0]) return a < b;
        return (a[1] - a[0]) > (b[1] - b[0]); });
    for (int i = 1; i <= ss(range); i += nsqrt)
    {
        int id = i / nsqrt;
        a[id].clear();
        l[id].clear();
        r[id].clear();
        fo(j, i, min(i + nsqrt - 1, ss(range)))
        {
            l[id].pb(range[j - 1][0]);
            r[id].pb(range[j - 1][1]);
            a[id].pb(range[j - 1][0], range[j - 1][1]);
        }
        len[id] = r[id].back() - l[id].back() + 1;
        sort(all(l[id]));
        sort(all(r[id]));
    }
}
int get(int L, int R, int k)
{
    int ans = 0;
    for (int i = 1; i <= ss(range); i += nsqrt)
    {
        int id = i / nsqrt;
        if (len[id] < k)
        {
            for (auto [u, v] : a[id])
            {
                bool ok = 1;
                if (v - u + 1 < k)
                    ok = 0;
                if (u > R - k + 1)
                    ok = 0;
                if (v < L + k - 1)
                    ok = 0;
                ans += ok;
            }
            return ans;
        }
        ans += ss(a[id]);
        ans -= ss(a[id]) - (lower_bound(all(l[id]), R - k + 2) - l[id].begin());
        ans -= lower_bound(all(r[id]), L + k - 1) - r[id].begin();
    }
    return ans;
}
int n, t, lastans;
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> t;
    vector<bool> del(n + 5,0);
    vii rr(n + 5);
    fo(xxx,1,n)
    {
        int ty;
        cin >> ty;
        if (ty == 1)
        {
            int l, r;
            cin >> l >> r;
            l = l ^ (t * lastans);
            r = r ^ (t * lastans);
            if (l > r)
                swap(l, r);
            qry.push_back({l, r, ++cnt});
            rr[cnt] = {l, r};
        }
        else if (ty == 2)
        {
            int id;
            cin >> id;
            del[id] = 1;
            qry.push_back({rr[id].fi, rr[id].se, -1});
        }
        else
        {
            int l, r, k;
            cin >> l >> r >> k;
            l = l ^ (t * lastans);
            r = r ^ (t * lastans);
            if (l > r)
                swap(l, r);
            if(r - l + 1 < k)
            {
                cout << 0;en;
                continue;
            }
            lastans = get(l, r, k);
            for (auto [u, v, id] : qry)
            {
                if (id == -1)
                {
                    bool ok = 1;
                    if (v - u + 1 < k)
                        ok = 0;
                    if (v < l + k - 1)
                        ok = 0;
                    if (u > r - k + 1)
                        ok = 0;
                    lastans -= ok;
                }
                else
                {
                    bool ok = 1;
                    if (v - u + 1 < k)
                        ok = 0;
                    if (v < l + k - 1)
                        ok = 0;
                    if (u > r - k + 1)
                        ok = 0;
                    lastans += ok;
                }
            }
            cout << lastans;
            en;
        }
        if (ss(qry) == nsqrt)
        {
            vector<array<int, 3>> newrange;
            for (auto [l, r, id] : range)
            {
                if (!del[id])
                    newrange.push_back({l, r, id});
            }
            for (auto [l, r, id] : qry)
                if (id != -1 and !del[id])
                {
                    newrange.push_back({l, r, id});
                }
            range = newrange;
            build();
            qry.clear();
        }
    }
}

Compilation message (stderr)

segments.cpp:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main()
      | ^~~~
segments.cpp: In function 'int main()':
segments.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 25 / 25