oj.uz

Submission #771951

# Submission time Handle Problem Language Result Execution time Memory
771951 2023-07-03T12:36:20 Z Sam_a17 New Home (APIO18_new_home) C++17
15 / 100
 5000 ms 230296 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 = 3e5 + 10, inf = 1e8;
vector<int> adj[N];
map<int, vector<pair<int, int>>> upds;
map<int, vector<int>> ups;
 
vector<pair<int, int>> a1[N], a2[N];
 
int n, k, q, answ[N];
int val[N];
 
multiset<int> mtik[N];
 
struct node {
  int x, t, a, b;
};
 
vector<node> cand;
 
void solve_() {
  cin >> n >> k >> q;
 
  int flag = 1;
  for(int i = 1; i <= n; i++) {
    int x, t, a, b; 
    cin >> x >> t >> a >> b;
    if(a != 1 || b != inf) {
      flag = 0;
    }
    cand.push_back({x, t, a, b});
  }
 
  if(flag) {
    vector<int> compress;
    for(auto i: cand) {
      adj[i.t].push_back(i.x);
    }
 
    int oki = 1;
    multiset<int> plus, minus;
 
    for(int i = 1; i <= k; i++) {
      sort(all(adj[i]));
      if(adj[i].empty()) {
        oki = 0;
      } else {
        plus.insert(adj[i][0]);
        val[i] = adj[i][0];
      }
 
      for(int j = 1; j < sz(adj[i]); j++) {
        int r = adj[i][j], l = adj[i][j - 1];
        int new_p = (r + l + 1) / 2;
        compress.push_back(new_p);
        if(new_p != r) {
          upds[new_p].emplace_back(r, i);
        }
      }
 
      for(auto j: adj[i]) {
        compress.push_back(j);
        upds[j].push_back({-j, i});
      }
    }
 
    for(int i = 1; i <= q; i++) {
      int l, y; cin >> l >> y;
      if(!oki) {
        cout << -1 << '\n';
        continue;
      } else {
        compress.push_back(l);
        ups[l].push_back(i);
      }
    }
 
    compress.push_back(1);
    compress.push_back(inf);
    sort(all(compress));
    uniq(compress);
 
    for(auto i: compress) {
      // dbg(upds[i])
      for(auto j: upds[i]) {
        if(val[j.second] > 0) {
          plus.erase(plus.find(val[j.second]));
        } else {
          minus.erase(minus.find(val[j.second]));
        }
 
        if(j.first > 0) {
          plus.insert(j.first);
        } else {
          minus.insert(j.first);
        }
        val[j.second] = j.first;
      }
 
      for(auto j: ups[i]) {
        int ans = 0;
        if(!plus.empty()) {
          ans = max(ans, *plus.rbegin() - i);
        } 
 
        if(!minus.empty()) {
          ans = max(ans, i + *minus.rbegin());
        }
 
        answ[j] = ans;
      }
    }
 
    for(int i = 1; i <= q; i++) {
      cout << answ[i] << '\n';
    }
  }
  else {
    vector<int> compress;
 
    for(auto i: cand) {
      compress.push_back(i.a);
      compress.push_back(i.b + 1);
 
      // upd2[i.a].push_back({i.x, i.t});
      // upd2[i.b + 1].push_back({-i.x, i.t});
    }
 
    vector<pair<int, int>> dat;
    for(int i = 1; i <= q; i++) {
      int l, y; cin >> l >> y;
      dat.push_back({l, y});
      // upds[y].push_back({l, i});
      compress.push_back(y);
    }
 
    sort(all(compress));
    uniq(compress);
    
    for(auto &i: cand) {
      i.a = lower_bound(all(compress), i.a) - compress.begin();
      i.b = lower_bound(all(compress), i.b + 1) - compress.begin();
      a1[i.a].push_back({i.x, i.t});
      a1[i.b].push_back({-i.x, i.t});
    }
    
    int itr = 1;
    for(auto &i: dat) {
      i.second = lower_bound(all(compress), i.second) - compress.begin();
      a2[i.second].push_back({i.first, itr});
      itr++;
    }
 
    for(int i = 0; i < sz(compress); i++) {
      for(auto j: a1[i]) {
        if(j.first > 0) {
          mtik[j.second].insert(j.first);
        } else {
          mtik[j.second].erase(mtik[j.second].find(-j.first));
        }
      }
      
      for(auto j: a2[i]) {
        int mx = 0;
        for(int cur = 1; cur <= k; cur++) {
          if(mtik[cur].empty()) {
            answ[j.second] = -1;
            break;
          }
          int min_dist = inf + 1;
          auto it = lower_bound(all(mtik[cur]), j.first);
          if(it != mtik[cur].end()) {
            min_dist = min(min_dist, *it - j.first);
          }
 
          if(it != mtik[cur].begin()) {
            it = prev(it);
            min_dist = min(min_dist, j.first - *it);
          }
 
          mx = max(mx, min_dist);
        }
 
        if(answ[j.second] != -1) {
          answ[j.second] = mx;
        }
      }
    }
 
    for(int i = 1; i <= q; i++) {
      cout << answ[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 setIO(std::string)':
new_home.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35540 KB Output is correct
2 Correct 15 ms 35552 KB Output is correct
3 Correct 15 ms 35532 KB Output is correct
4 Correct 15 ms 35564 KB Output is correct
5 Correct 16 ms 35540 KB Output is correct
6 Correct 22 ms 35552 KB Output is correct
7 Correct 16 ms 35540 KB Output is correct
8 Correct 16 ms 35580 KB Output is correct
9 Correct 16 ms 35668 KB Output is correct
10 Correct 18 ms 35576 KB Output is correct
11 Correct 19 ms 35524 KB Output is correct
12 Correct 16 ms 35548 KB Output is correct
13 Correct 20 ms 35592 KB Output is correct
14 Correct 16 ms 35524 KB Output is correct
15 Correct 16 ms 35540 KB Output is correct
16 Correct 17 ms 35536 KB Output is correct
17 Correct 19 ms 35556 KB Output is correct
18 Correct 16 ms 35560 KB Output is correct
19 Correct 19 ms 35664 KB Output is correct
20 Correct 20 ms 35576 KB Output is correct
21 Correct 18 ms 35540 KB Output is correct
22 Correct 17 ms 35540 KB Output is correct
23 Correct 17 ms 35580 KB Output is correct
24 Correct 16 ms 35568 KB Output is correct
25 Correct 15 ms 35540 KB Output is correct
26 Correct 15 ms 35540 KB Output is correct
27 Correct 15 ms 35540 KB Output is correct
28 Correct 19 ms 35600 KB Output is correct
29 Correct 17 ms 35580 KB Output is correct
30 Correct 16 ms 35540 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35540 KB Output is correct
2 Correct 15 ms 35552 KB Output is correct
3 Correct 15 ms 35532 KB Output is correct
4 Correct 15 ms 35564 KB Output is correct
5 Correct 16 ms 35540 KB Output is correct
6 Correct 22 ms 35552 KB Output is correct
7 Correct 16 ms 35540 KB Output is correct
8 Correct 16 ms 35580 KB Output is correct
9 Correct 16 ms 35668 KB Output is correct
10 Correct 18 ms 35576 KB Output is correct
11 Correct 19 ms 35524 KB Output is correct
12 Correct 16 ms 35548 KB Output is correct
13 Correct 20 ms 35592 KB Output is correct
14 Correct 16 ms 35524 KB Output is correct
15 Correct 16 ms 35540 KB Output is correct
16 Correct 17 ms 35536 KB Output is correct
17 Correct 19 ms 35556 KB Output is correct
18 Correct 16 ms 35560 KB Output is correct
19 Correct 19 ms 35664 KB Output is correct
20 Correct 20 ms 35576 KB Output is correct
21 Correct 18 ms 35540 KB Output is correct
22 Correct 17 ms 35540 KB Output is correct
23 Correct 17 ms 35580 KB Output is correct
24 Correct 16 ms 35568 KB Output is correct
25 Correct 15 ms 35540 KB Output is correct
26 Correct 15 ms 35540 KB Output is correct
27 Correct 15 ms 35540 KB Output is correct
28 Correct 19 ms 35600 KB Output is correct
29 Correct 17 ms 35580 KB Output is correct
30 Correct 16 ms 35540 KB Output is correct
31 Execution timed out 5022 ms 48096 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1614 ms 223860 KB Output is correct
2 Correct 1083 ms 228608 KB Output is correct
3 Correct 1102 ms 197432 KB Output is correct
4 Correct 1587 ms 219056 KB Output is correct
5 Correct 996 ms 228064 KB Output is correct
6 Correct 992 ms 228536 KB Output is correct
7 Correct 1083 ms 197416 KB Output is correct
8 Correct 1540 ms 218796 KB Output is correct
9 Correct 1619 ms 227332 KB Output is correct
10 Correct 1380 ms 230296 KB Output is correct
11 Correct 943 ms 226140 KB Output is correct
12 Correct 1144 ms 229012 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 325 ms 131748 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35540 KB Output is correct
2 Correct 15 ms 35552 KB Output is correct
3 Correct 15 ms 35532 KB Output is correct
4 Correct 15 ms 35564 KB Output is correct
5 Correct 16 ms 35540 KB Output is correct
6 Correct 22 ms 35552 KB Output is correct
7 Correct 16 ms 35540 KB Output is correct
8 Correct 16 ms 35580 KB Output is correct
9 Correct 16 ms 35668 KB Output is correct
10 Correct 18 ms 35576 KB Output is correct
11 Correct 19 ms 35524 KB Output is correct
12 Correct 16 ms 35548 KB Output is correct
13 Correct 20 ms 35592 KB Output is correct
14 Correct 16 ms 35524 KB Output is correct
15 Correct 16 ms 35540 KB Output is correct
16 Correct 17 ms 35536 KB Output is correct
17 Correct 19 ms 35556 KB Output is correct
18 Correct 16 ms 35560 KB Output is correct
19 Correct 19 ms 35664 KB Output is correct
20 Correct 20 ms 35576 KB Output is correct
21 Correct 18 ms 35540 KB Output is correct
22 Correct 17 ms 35540 KB Output is correct
23 Correct 17 ms 35580 KB Output is correct
24 Correct 16 ms 35568 KB Output is correct
25 Correct 15 ms 35540 KB Output is correct
26 Correct 15 ms 35540 KB Output is correct
27 Correct 15 ms 35540 KB Output is correct
28 Correct 19 ms 35600 KB Output is correct
29 Correct 17 ms 35580 KB Output is correct
30 Correct 16 ms 35540 KB Output is correct
31 Execution timed out 5022 ms 48096 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35540 KB Output is correct
2 Correct 15 ms 35552 KB Output is correct
3 Correct 15 ms 35532 KB Output is correct
4 Correct 15 ms 35564 KB Output is correct
5 Correct 16 ms 35540 KB Output is correct
6 Correct 22 ms 35552 KB Output is correct
7 Correct 16 ms 35540 KB Output is correct
8 Correct 16 ms 35580 KB Output is correct
9 Correct 16 ms 35668 KB Output is correct
10 Correct 18 ms 35576 KB Output is correct
11 Correct 19 ms 35524 KB Output is correct
12 Correct 16 ms 35548 KB Output is correct
13 Correct 20 ms 35592 KB Output is correct
14 Correct 16 ms 35524 KB Output is correct
15 Correct 16 ms 35540 KB Output is correct
16 Correct 17 ms 35536 KB Output is correct
17 Correct 19 ms 35556 KB Output is correct
18 Correct 16 ms 35560 KB Output is correct
19 Correct 19 ms 35664 KB Output is correct
20 Correct 20 ms 35576 KB Output is correct
21 Correct 18 ms 35540 KB Output is correct
22 Correct 17 ms 35540 KB Output is correct
23 Correct 17 ms 35580 KB Output is correct
24 Correct 16 ms 35568 KB Output is correct
25 Correct 15 ms 35540 KB Output is correct
26 Correct 15 ms 35540 KB Output is correct
27 Correct 15 ms 35540 KB Output is correct
28 Correct 19 ms 35600 KB Output is correct
29 Correct 17 ms 35580 KB Output is correct
30 Correct 16 ms 35540 KB Output is correct
31 Execution timed out 5022 ms 48096 KB Time limit exceeded
32 Halted 0 ms 0 KB -