답안 #777667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777667 2023-07-09T12:39:52 Z Sam_a17 새 집 (APIO18_new_home) C++17
10 / 100
5000 ms 584840 KB
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int)x.size()
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount
 
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
#define ll long long
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// Indexed Set  
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
// template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(Tree <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
 
 
// for random generations
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 myrand(131);
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  // if(str == "input") {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
  // } else if(str != "") {
    // freopen((str + ".in").c_str(), "r", stdin);
    // freopen((str + ".out").c_str(), "w", stdout);
  // }
}
 
const int N = 2e6 + 10 + 4e5 + 10, maxM = 3e5 + 10, inf = 1e8, infi = 2e9 + 10;
vector<pair<pair<int, int>, int>> to_add[N];
int n, k, q;
bool oki = 1;
 
struct node {
  int x, t, a, b;
};
 
vector<node> cand;

struct segTreeMax {  // Range Queries
  multiset<int> mt[N];
  vector<int> mTree;
  int size, sub;

  void init(ll n) {
    size = 1;
    while(size < n)  {
      size *= 2;
    }
    mTree.assign(2 * size - 1, 0);
  }

  void upd(int u, ll v, int x, int lx, int rx) { // set value at pos u
    if(rx - lx == 1) {
      x -= sub;
      if(v >= 0) {
        mt[x].insert(v);
      } else {
        assert(mt[x].find(-v) != mt[x].end());
        mt[x].erase(mt[x].find(-v));
      }
      assert(sz(mt[x]) <= 5);

      if(!mt[x].empty()) {
        mTree[x + sub] = *prev(mt[x].end());
      } else {
        mTree[x + sub] = -1;
      }
      return;
    }

    int m = (lx + rx) / 2;
    if(u < m) {
      upd(u, v, 2 * x + 1, lx, m);
    }else {
      upd(u, v, 2 * x + 2, m, rx);
    }
    mTree[x] = max(mTree[2 * x + 1], mTree[2 * x + 2]);
  }

  void upd(int u, ll v) {
    upd(u, v, 0, 0, size);
  }

  int gt(int u, int x, int lx, int rx) { // set value at pos u
    if(rx - lx == 1) {
      sub = x;
      return x;
    }

    int m = (lx + rx) / 2;
    if(u < m) {
      return gt(u, 2 * x + 1, lx, m);
    }else {
      return gt(u, 2 * x + 2, m, rx);
    }
  }

  int gt(int u) {
    return gt(u, 0, 0, size);
  }

  int qry(int l, int r, int x, int lx, int rx) { // range queries
    if(l >= rx || lx >= r) {
      return -1;
    }

    if(lx >= l && r >= rx) {
      return mTree[x];
    }

    int m = (rx + lx) / 2;
    int s1 = qry(l, r, 2 * x + 1, lx, m);
    int s2 = qry(l, r, 2 * x + 2, m, rx);
    return max(s1, s2);
  }

  int qry(int l, int r) {
    return qry(l, r, 0,0,size);
  }
};

struct segTreeMin {  // Range Queries
  multiset<int> mt[N];
  vector<int> mTree;
  int size;
  int sub;

  void init(ll n) {
    size = 1;
    while(size < n)  {
      size *= 2;
    }
    mTree.assign(2 * size - 1, INT32_MAX);
  }

  int ind(int xx) {
    if(xx >= sub) {
      return xx - sub;
    } else {
      return xx;
    }
  }

  void upd(int u, ll v, int x, int lx, int rx) { // set value at pos u
    if(rx - lx == 1) {
      x -= sub;
      if(v >= 0) {
        mt[x].insert(v);
      } else {
        assert(mt[x].find(-v) != mt[x].end());
        mt[x].erase(mt[x].find(-v));
      }

      if(!mt[x].empty()) {
        mTree[x + sub] = *mt[x].begin();
      } else {
        mTree[x + sub] = INT32_MAX;
      }
      return;
    }

    int m = (lx + rx) / 2;
    if(u < m) {
      upd(u, v, 2 * x + 1, lx, m);
    }else {
      upd(u, v, 2 * x + 2, m, rx);
    }
    mTree[x] = min(mTree[2 * x + 1], mTree[2 * x + 2]);
  }

  void upd(int u, ll v) {
    upd(u, v, 0, 0, size);
  }

  int gt(int u, int x, int lx, int rx) { // set value at pos u
    if(rx - lx == 1) {
      sub = x;
      return x;
    }

    int m = (lx + rx) / 2;
    if(u < m) {
      return gt(u, 2 * x + 1, lx, m);
    }else {
      return gt(u, 2 * x + 2, m, rx);
    }
  }

  int gt(int u) {
    return gt(u, 0, 0, size);
  }

  int qry(int l, int r, int x, int lx, int rx) { // range queries
    if(l >= rx || lx >= r) {
      return INT32_MAX;
    }

    if(lx >= l && r >= rx) {
      return mTree[x];
    }

    int m = (rx + lx) / 2;
    int s1 = qry(l, r, 2 * x + 1, lx, m);
    int s2 = qry(l, r, 2 * x + 2, m, rx);
    return min(s1, s2);
  }

  int qry(int l, int r) {
    return qry(l, r, 0,0,size);
  }
};

segTreeMax rs;
segTreeMin ls;

vector<int> compress_times, compress_locations;
map<int, int> mx_col[maxM];
int pat[maxM];

int get(int val) {
  return lower_bound(all(compress_locations), val) - compress_locations.begin();
}

void add_interval(int type, int l, int r) {
  int mid = (l + r + 1) / 2;
  l = get(l);
  r = get(r);
  int midone = get(mid - 1);
  mid = midone + 1;
  
  if(mid <= r) {
    rs.upd(mid, r);
  }
  if(l < mid) {
    ls.upd(midone, l);
  }
}

void del_interval(int type, int l, int r) {
  int mid = (l + r + 1) / 2;
  
  l = get(l);
  r = get(r);
  int midone = get(mid - 1);
  mid = midone + 1;

  if(mid <= r) rs.upd(mid, -r);
  if(l < mid) ls.upd(midone, -l);
}

void solve_() {
  cin >> n >> k >> q;
 
  for(int i = 1; i <= n; i++) {
    int x, t, a, b; 
    cin >> x >> t >> a >> b;

    if(a != 1) {
      oki = 1;
    }
    
    compress_times.push_back(a);
    compress_times.push_back(b + 1);

    compress_locations.push_back(x);

    cand.push_back({x, t, a, b});
  }

  vector<pair<int, int>> queries;
  for(int i = 1; i <= q; i++) {
    int l, y; cin >> l >> y;
    compress_locations.push_back(l);
    compress_times.push_back(y);
    queries.emplace_back(l, y);
  }

  compress_locations.push_back(-infi);
  compress_locations.push_back(infi);
  
  sort(all(compress_times));
  uniq(compress_times);


  for(auto &i: cand) {
    i.a = lower_bound(all(compress_times), i.a) - compress_times.begin();
    i.b = lower_bound(all(compress_times), i.b + 1) - compress_times.begin();

    to_add[i.a].push_back({{i.x, i.t}, 1});
    to_add[i.b].push_back({{i.x, i.t}, 2});
  } 

  {
    vector<node> vi;
    cand.swap(vi);
  }

  for(int i = 1; i <= k; i++) {
    mx_col[i][-infi] = 1;
    mx_col[i][infi] = 1;
  }

  for(int i = 0; i < sz(compress_times); i++) {
    for(auto cc: to_add[i]) {
      if(cc.second == 1) { 
        auto j = cc.first;
        if(mx_col[j.second].find(j.first) != mx_col[j.second].end()) {
          mx_col[j.second][j.first]++;
          continue;
        }

        mx_col[j.second][j.first] = 1;
        auto it = mx_col[j.second].find(j.first);
        auto it_prev = prev(it), it_next = next(it);

        int mid1 = (it_next->first + j.first + 1) / 2;
        int mid2 = (it_prev->first + j.first + 1) / 2;

        compress_locations.push_back(mid1);
        compress_locations.push_back(mid1 - 1);

        compress_locations.push_back(mid2);
        compress_locations.push_back(mid2 - 1);
      } else if(cc.second == 2) {
        auto j = cc.first;
        mx_col[j.second][j.first]--;
        if(mx_col[j.second][j.first] == 0) {

          auto it = mx_col[j.second].find(j.first);
          auto it_prev = prev(it), it_next = next(it);

          int mid1 = (it_next->first + it_prev->first + 1) / 2;
          
          compress_locations.push_back(mid1);
          compress_locations.push_back(mid1 - 1);
  
          mx_col[j.second].erase(j.first);
        }
      } 
    }
  }

  int it = 1;
  for(auto &i: queries) {
    i.second = lower_bound(all(compress_times), i.second) - compress_times.begin();
    to_add[i.second].push_back({{i.first, it}, 0});
    it++;
  }

  sort(all(compress_locations));
  uniq(compress_locations);
  ls.init(sz(compress_locations) + 2);
  rs.init(sz(compress_locations) + 2);
  rs.gt(0);
  ls.gt(0);

  for(int i = 1; i <= k; i++) {
    mx_col[i].clear();
    
    mx_col[i][-infi] = 1;
    mx_col[i][infi] = 1;
  }

  vector<bool> empty(k + 1, true);
  int emp = k;
  for(int i = 0; i < sz(compress_times); i++) {
    for(auto cc: to_add[i]) {
      if(cc.second == 1) { 
        auto j = cc.first;
        if(mx_col[j.second].find(j.first) != mx_col[j.second].end()) {
          mx_col[j.second][j.first]++;
          continue;
        }

        mx_col[j.second][j.first] = 1;
        if(sz(mx_col[j.second]) == 3) {
          empty[j.second] = false;
          emp--;
        }

        auto it = mx_col[j.second].find(j.first);
        auto it_prev = prev(it), it_next = next(it);

        int mid1 = (it_next->first + j.first + 1) / 2;
        int mid2 = (it_prev->first + j.first + 1) / 2;

        add_interval(j.second, it_prev->first, j.first);
        add_interval(j.second, j.first, it_next->first);

        if(it_prev->first != -infi || it_next->first != infi) {
          del_interval(j.second, it_prev->first, it_next->first);
        }
      } else if(cc.second == 2) {
        auto j = cc.first;
        mx_col[j.second][j.first]--;
        if(mx_col[j.second][j.first] == 0) {

          auto it = mx_col[j.second].find(j.first);
          if(sz(mx_col[j.second]) == 3) {
            empty[j.second] = true;
            emp++;
          }

          auto it_prev = prev(it), it_next = next(it);
          del_interval(j.second, it_prev->first, j.first);
          del_interval(j.second, j.first, it_next->first);

          if(it_prev->first != -infi || it_next->first != infi) {
            add_interval(j.second, it_prev->first, it_next->first);
          }

          mx_col[j.second].erase(j.first);
        }
      } else {
        auto j = cc.first;
        if(emp) {
          pat[j.second] = -1;
        } else {
          int cur = lower_bound(all(compress_locations), j.first) - compress_locations.begin();
          int li = ls.qry(cur, sz(compress_locations) + 1);
          int ri = rs.qry(0, cur + 1);

          if(li <= cur) {
            pat[j.second] = max(pat[j.second], j.first - compress_locations[li]);
          }

          if(ri >= cur) {
            pat[j.second] = max(pat[j.second], compress_locations[ri] - j.first);
          }
        }
      }
    }
  }

  for(int i = 1; i <= q; i++) {
    cout << pat[i] << '\n';
  }
 }
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    for(int i = 1; i <= test_case; i++) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

new_home.cpp: In function 'void solve_()':
new_home.cpp:440:13: warning: unused variable 'mid1' [-Wunused-variable]
  440 |         int mid1 = (it_next->first + j.first + 1) / 2;
      |             ^~~~
new_home.cpp:441:13: warning: unused variable 'mid2' [-Wunused-variable]
  441 |         int mid2 = (it_prev->first + j.first + 1) / 2;
      |             ^~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 480 ms 584840 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 480 ms 584840 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 4880 ms 459352 KB Output is correct
2 Correct 4797 ms 439360 KB Output is correct
3 Correct 3151 ms 464352 KB Output is correct
4 Correct 4272 ms 466316 KB Output is correct
5 Correct 4482 ms 439024 KB Output is correct
6 Correct 4777 ms 439532 KB Output is correct
7 Correct 2891 ms 464324 KB Output is correct
8 Correct 3544 ms 466624 KB Output is correct
9 Correct 3726 ms 450688 KB Output is correct
10 Correct 4228 ms 439968 KB Output is correct
11 Correct 2377 ms 438088 KB Output is correct
12 Correct 2543 ms 439448 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5048 ms 447380 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 480 ms 584840 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 480 ms 584840 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -