Submission #1104502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104502		Boycl07	New Home (APIO18_new_home)	C++17	100 / 100	2625 ms	118616 KiB

new_home

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

typedef long long ll;
typedef unsigned long long ull;


#define rep(i, n) for(int i = 1; (i) <= (n); ++i)
#define forn(i, l, r) for(int i = (l); i <= (r); ++i)
#define ford(i, r, l) for(int i = (r); i >= (l); --i)
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "note"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const int N = 6e5 + 3;
const int M = 5e3 + 100;
const int LIM = 5e5 + 3;
const int LOG = 16;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 33;
const ll LINF = 2e16 + 33;


int n, k, q;

multiset<int> s[N];
int st[N << 1];

int X[N], T[N], A[N], B[N];
int lim;

void update(int id, int val)
{
    for(st[id += lim] = val; id >>= 1;) st[id] = max(st[id << 1], st[id << 1 | 1]);
}

int get(int l, int r)
{
    int res = -INF;
    for(l += lim, r += lim + 1; l < r; l >>= 1, r >>= 1)
    {
        if(l & 1) maximize(res, st[l++]);
        if(r & 1) maximize(res, st[--r]);
    }
    return res;
}

int ans[N];

void solve()
{

    cin >> n >> k >> q;

    vector<pii> zip;

    vector<array<int, 4>> lines;
    lim = n + k;
    rep(i, n) cin >> X[i] >> T[i] >> A[i] >> B[i], zip.pb({X[i], i});
    rep(i, k) s[i].insert(i), s[i].insert(INF), update(i, INF);

    sort(all(zip));
    rep(i, n)
    {
        X[i] = lower_bound(all(zip), make_pair(X[i], i)) - zip.begin() + 1;

        lines.pb({A[i], X[i] + k, T[i], 0});
        lines.pb({B[i] + 1, X[i] + k, T[i], 1});

    }
    rep(i, q)
    {
        int l, y;
        cin >> y >> l;
        lines.pb({l, INF, y, -i});
    }

    sort(all(lines));

    for(auto &[x, y, t, type] : lines)
    {
        if(type == 0)
        {
            auto it = s[t].upper_bound(y);
            int r = *it;
            int l = *(--it);

            update(l, y);
            update(y, r);
            s[t].insert(y);
        }
        else if(type < 0)
        {
            int lb = 0, rb = 1e9, res = -1;
            while(lb <= rb)
            {
                int mid = lb + rb >> 1;
                int l = lower_bound(all(zip), make_pair(t - mid, -INF)) - zip.begin() + k;
                int r = upper_bound(all(zip), make_pair(t + mid, INF)) - zip.begin() + k;

                if(get(1, l) <= r) res = mid, rb = mid - 1;
                else lb = mid + 1;
            }
            ans[-type] = res;
        }
        else
        {
            s[t].erase(s[t].find(y));
            auto it = s[t].upper_bound(y);
            int r = *it;
            int l = *(--it);
            update(l, r);
            update(y, -INF);
        }
    }
    rep(i, q) cout << ans[i] << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int TC = 1;

    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }



    while(TC--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:114:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |                 int mid = lb + rb >> 1;
      |                           ~~~^~~~
new_home.cpp: In function 'int main()':
new_home.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20