Submission #900228

#	Time	Username	Problem	Language	Result	Execution time	Memory
900228		bobbilyking	Sweeping (JOI20_sweeping)	C++17	1 / 100	17 ms	856 KiB

sweeping

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

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

typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

#define M 1000000007 // 998244353

using T=pair<int, int>;
T merge(T a, T b) {
    return {max(a.K,b.K),max(a.V,b.V)};
}
T id = T(-1, -1);

struct SparseTable {
    int n,log2=0;
    vector<vector<T>> a = {{}};
    SparseTable(const vector<T>& v) {
        n = v.size();
        while((1<<log2) <= n) {
            ++log2;
        }
        a.resize(log2);
        a[0] = v;
        for(int i=1,len=1;i<log2;++i,len*=2) {
            a[i].resize(n + 1 - (1<<i));
            for(int j=0;j<a[i].size();++j) {
                a[i][j] = merge(a[i-1][j], a[i-1][j + len]);
            }
        }
    }
    SparseTable(){}
    T query(int l, int r) { // [l,r)
        if (l >= r) return id;
        int len = __lg(r-l);
        return merge(a[len][l], a[len][r- (1<<len)]);
    }
} seg;

int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    G(n) G(m) G(q)

    if (m > 3000 || q > 6000) EX(-1)

    vector<pair<pl, ll>> dusts;
    vector<T> ev(1, id);
    F(i, 0, m) {
        G(x) G(y)
        dusts.emplace_back(pair(x, y), 0);
    }
    vector<pl> requests;
    F(i, 0, q) {
        G(t) if (t==1) {
           G(p)   --p;
           ev.emplace_back(id); 
           requests.emplace_back(p, ev.size());
        } else if (t == 2) {
            G(l)
            ev.emplace_back(n-l, -1);
        } else if (t == 3) {
            G(l)
            ev.emplace_back(-1, n-l);
        } else {
            G(a) G(b)
            dusts.emplace_back(pair(a, b), ev.size());
            ev.emplace_back(id);
        }
    }

    // SparseTable sparse(ev);
    for (auto [didx, ed]: requests) {
        auto [coords, st] = dusts[didx];
        ll l = st, r = ed;

        auto [x, y] = coords;
        F(j, st, ed) {
            auto [a, b] = ev[j];
            if (max(x, a) + max(b, y) <= n) x = max(x, a), y = max(b, y);
        }
        cout << x << " " << y << '\n';
    }
}

Compilation message (stderr)

sweeping.cpp: In constructor 'SparseTable::SparseTable(const std::vector<std::pair<int, int> >&)':
sweeping.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int j=0;j<a[i].size();++j) {
      |                         ~^~~~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:95:12: warning: unused variable 'l' [-Wunused-variable]
   95 |         ll l = st, r = ed;
      |            ^
sweeping.cpp:95:20: warning: unused variable 'r' [-Wunused-variable]
   95 |         ll l = st, r = ed;
      |                    ^

• Subtask 1: 1 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25