oj.uz

Submission #900234

# Submission time Handle Problem Language Result Execution time Memory
900234 2024-01-07T23:25:49 Z bobbilyking Sweeping (JOI20_sweeping) C++17
1 / 100
 343 ms 179360 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 600 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 18 ms 664 KB Output is correct
4 Correct 16 ms 756 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 22 ms 600 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 343 ms 179360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 318 ms 177420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 318 ms 177420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 600 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 18 ms 664 KB Output is correct
4 Correct 16 ms 756 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 22 ms 600 KB Output is correct
7 Incorrect 343 ms 179360 KB Output isn't correct
8 Halted 0 ms 0 KB -