Submission #374785

#	Time	Username	Problem	Language	Result	Execution time	Memory
374785		Mamnoon_Siam	Sweeping (JOI20_sweeping)	C++17	10 / 100	1940 ms	145220 KiB

sweeping

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

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
using tri = array<int, 3>;

inline void chkmax(int& x, int y) {
  x = y > x ? y : x;
}

const int N = 2e6 + 5;

struct Node {
  Node *l = 0, *r = 0;
  int lo, hi;
  int lz = INT_MIN;
  Node(int _lo, int _hi) : lo(_lo), hi(_hi) {
    if(lo+1 < hi) {
      int mid = lo + (hi - lo) / 2;
      l = new Node(lo, mid), r = new Node(mid, hi);
    }
  }
  void __chkmax(int L, int R, int x) {
    if(R <= lo or hi <= L) return;
    if(L <= lo and hi <= R) upd(x);
    else {
      push();
      l -> __chkmax(L, R, x);
      r -> __chkmax(L, R, x);
    }
  }
  void upd(int x) {
    chkmax(lz, x);
  }
  void push() {
    if(lo+1 < hi and lz != INT_MIN) {
      l -> upd(lz);
      r -> upd(lz);
    }
    lz = INT_MIN;
  }
  void update(int p, int x) {
    if(lo+1 == hi) lz = x;
    else {
      int mid = lo + (hi - lo) / 2;
      push();
      if(p < mid) l -> update(p, x);
      else r -> update(p, x);
    }
  }
  int query(int p) {
    if(lo+1 == hi) return lz;
    else {
      int mid = lo + (hi - lo) / 2;
      push();
      if(p < mid) return l -> query(p);
      else return r -> query(p);
    }
  }
};

int n, m, q;
vector<ii> v;
vector<tri> vs;
vi ys;
vector<ii> queries;
vi where; // wheres the i-th points after sorting by y

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d %d %d", &n, &m, &q);
  for(int i = 0; i < m; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    v.emplace_back(x, y);
    vs.push_back({y, x, i});
  }
  for(int i = 0; i < q; ++i) {
    int t, x, y;
    scanf("%d %d", &t, &x);
    int s = sz(vs);
    if(t == 4) scanf("%d", &y), v.emplace_back(x, y), vs.push_back({y, x, s});
    queries.emplace_back(t, x);
  }
  sort(all(vs));
  where.resize(sz(vs));
  for(int i = 0; i < sz(vs); ++i) {
    where[vs[i][2]] = i;
    ys.emplace_back(vs[i][0]);
  }
  Node* tr = new Node(0, sz(ys));
  int ptr = 0;
  for(; ptr < m; ++ptr) {
    tr -> update(where[ptr], v[ptr].fi);
  }
  for(auto [t, l] : queries) {
    if(t == 1) {
      printf("%d %d\n", tr -> query(where[l-1]), v[l-1].se);
    } else if(t == 2) {
      int i = int(upper_bound(all(ys), l) - ys.begin());
      tr -> __chkmax(0, i, n-l);
    } else { // 4
      tr -> update(where[ptr], v[ptr].fi);
      ++ptr;
    }
  }
  return 0;
}
/*
* use std::array instead of std::vector, if u can
* overflow?
* array bounds
*/

Compilation message (stderr)

sweeping.cpp: In function 'int main(int, const char**)':
sweeping.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |   scanf("%d %d %d", &n, &m, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |     scanf("%d %d", &t, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:91:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |     if(t == 4) scanf("%d", &y), v.emplace_back(x, y), vs.push_back({y, x, s});
      |                ~~~~~^~~~~~~~~~

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