Submission #900234

#	Time	Username	Problem	Language	Result	Execution time	Memory
900234		bobbilyking	Sweeping (JOI20_sweeping)	C++17	1 / 100	343 ms	179360 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>;

ll n;
// only works if op == 2 only (second subtask)
T merge(T a, T b) {
    if (max(a.K,b.K) + max(a.V,b.V) <= n) return pair(max(a.K, b.K), max(a.V, b.V));
    return a;
}

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)]);
        
    }
};

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);
    cin >> n; G(m) G(q)

    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);
        }
    }

    if (m <= 2000 and q <= 5000) {
        for (auto [didx, ed]: requests) {
            auto [coords, st] = dusts[didx];
            ll l = st, r = ed;

            F(j, st, ed) coords = merge(coords, ev[j]);

            auto [x, y] = coords;
            cout << x << " " << y << '\n';
        }
    } else {
        SparseTable seg(ev);
        for (auto [didx, ed]: requests) {
            auto [coords, st] = dusts[didx];
            ll l = st, r = ed;
                        
            auto [x, y] = merge(coords, seg.query(l, r));
            cout << x << " " << y << '\n';
        }

    }


    
}

Compilation message (stderr)

sweeping.cpp: In constructor 'SparseTable::SparseTable(const std::vector<std::pair<int, int> >&)':
sweeping.cpp:49: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]
   49 |             for(int j=0;j<a[i].size();++j) {
      |                         ~^~~~~~~~~~~~
sweeping.cpp: In function 'int main()':
sweeping.cpp:100:16: warning: unused variable 'l' [-Wunused-variable]
  100 |             ll l = st, r = ed;
      |                ^
sweeping.cpp:100:24: warning: unused variable 'r' [-Wunused-variable]
  100 |             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