oj.uz

Submission #771639

# Submission time Handle Problem Language Result Execution time Memory
771639 2023-07-03T07:40:13 Z Sam_a17 New Home (APIO18_new_home) C++17
15 / 100
 5000 ms 219148 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 20 ms 35556 KB Output is correct
2 Correct 18 ms 35560 KB Output is correct
3 Correct 18 ms 35564 KB Output is correct
4 Correct 18 ms 35548 KB Output is correct
5 Correct 18 ms 35552 KB Output is correct
6 Correct 20 ms 35612 KB Output is correct
7 Correct 20 ms 35580 KB Output is correct
8 Correct 20 ms 35576 KB Output is correct
9 Correct 18 ms 35576 KB Output is correct
10 Correct 20 ms 35572 KB Output is correct
11 Correct 18 ms 35540 KB Output is correct
12 Correct 20 ms 35540 KB Output is correct
13 Correct 19 ms 35540 KB Output is correct
14 Correct 18 ms 35572 KB Output is correct
15 Correct 19 ms 35624 KB Output is correct
16 Correct 20 ms 35620 KB Output is correct
17 Correct 18 ms 35540 KB Output is correct
18 Correct 19 ms 35540 KB Output is correct
19 Correct 19 ms 35576 KB Output is correct
20 Correct 19 ms 35560 KB Output is correct
21 Correct 18 ms 35576 KB Output is correct
22 Correct 19 ms 35616 KB Output is correct
23 Correct 20 ms 35568 KB Output is correct
24 Correct 22 ms 35540 KB Output is correct
25 Correct 19 ms 35628 KB Output is correct
26 Correct 19 ms 35568 KB Output is correct
27 Correct 18 ms 35572 KB Output is correct
28 Correct 18 ms 35568 KB Output is correct
29 Correct 18 ms 35532 KB Output is correct
30 Correct 19 ms 35576 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35556 KB Output is correct
2 Correct 18 ms 35560 KB Output is correct
3 Correct 18 ms 35564 KB Output is correct
4 Correct 18 ms 35548 KB Output is correct
5 Correct 18 ms 35552 KB Output is correct
6 Correct 20 ms 35612 KB Output is correct
7 Correct 20 ms 35580 KB Output is correct
8 Correct 20 ms 35576 KB Output is correct
9 Correct 18 ms 35576 KB Output is correct
10 Correct 20 ms 35572 KB Output is correct
11 Correct 18 ms 35540 KB Output is correct
12 Correct 20 ms 35540 KB Output is correct
13 Correct 19 ms 35540 KB Output is correct
14 Correct 18 ms 35572 KB Output is correct
15 Correct 19 ms 35624 KB Output is correct
16 Correct 20 ms 35620 KB Output is correct
17 Correct 18 ms 35540 KB Output is correct
18 Correct 19 ms 35540 KB Output is correct
19 Correct 19 ms 35576 KB Output is correct
20 Correct 19 ms 35560 KB Output is correct
21 Correct 18 ms 35576 KB Output is correct
22 Correct 19 ms 35616 KB Output is correct
23 Correct 20 ms 35568 KB Output is correct
24 Correct 22 ms 35540 KB Output is correct
25 Correct 19 ms 35628 KB Output is correct
26 Correct 19 ms 35568 KB Output is correct
27 Correct 18 ms 35572 KB Output is correct
28 Correct 18 ms 35568 KB Output is correct
29 Correct 18 ms 35532 KB Output is correct
30 Correct 19 ms 35576 KB Output is correct
31 Execution timed out 5104 ms 47908 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1676 ms 214008 KB Output is correct
2 Correct 1061 ms 219148 KB Output is correct
3 Correct 1098 ms 186036 KB Output is correct
4 Correct 1593 ms 206620 KB Output is correct
5 Correct 955 ms 216180 KB Output is correct
6 Correct 995 ms 216388 KB Output is correct
7 Correct 1057 ms 183852 KB Output is correct
8 Correct 1621 ms 205368 KB Output is correct
9 Correct 1554 ms 213876 KB Output is correct
10 Correct 1396 ms 217140 KB Output is correct
11 Correct 945 ms 213644 KB Output is correct
12 Correct 1222 ms 216104 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 325 ms 118620 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 20 ms 35556 KB Output is correct
2 Correct 18 ms 35560 KB Output is correct
3 Correct 18 ms 35564 KB Output is correct
4 Correct 18 ms 35548 KB Output is correct
5 Correct 18 ms 35552 KB Output is correct
6 Correct 20 ms 35612 KB Output is correct
7 Correct 20 ms 35580 KB Output is correct
8 Correct 20 ms 35576 KB Output is correct
9 Correct 18 ms 35576 KB Output is correct
10 Correct 20 ms 35572 KB Output is correct
11 Correct 18 ms 35540 KB Output is correct
12 Correct 20 ms 35540 KB Output is correct
13 Correct 19 ms 35540 KB Output is correct
14 Correct 18 ms 35572 KB Output is correct
15 Correct 19 ms 35624 KB Output is correct
16 Correct 20 ms 35620 KB Output is correct
17 Correct 18 ms 35540 KB Output is correct
18 Correct 19 ms 35540 KB Output is correct
19 Correct 19 ms 35576 KB Output is correct
20 Correct 19 ms 35560 KB Output is correct
21 Correct 18 ms 35576 KB Output is correct
22 Correct 19 ms 35616 KB Output is correct
23 Correct 20 ms 35568 KB Output is correct
24 Correct 22 ms 35540 KB Output is correct
25 Correct 19 ms 35628 KB Output is correct
26 Correct 19 ms 35568 KB Output is correct
27 Correct 18 ms 35572 KB Output is correct
28 Correct 18 ms 35568 KB Output is correct
29 Correct 18 ms 35532 KB Output is correct
30 Correct 19 ms 35576 KB Output is correct
31 Execution timed out 5104 ms 47908 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35556 KB Output is correct
2 Correct 18 ms 35560 KB Output is correct
3 Correct 18 ms 35564 KB Output is correct
4 Correct 18 ms 35548 KB Output is correct
5 Correct 18 ms 35552 KB Output is correct
6 Correct 20 ms 35612 KB Output is correct
7 Correct 20 ms 35580 KB Output is correct
8 Correct 20 ms 35576 KB Output is correct
9 Correct 18 ms 35576 KB Output is correct
10 Correct 20 ms 35572 KB Output is correct
11 Correct 18 ms 35540 KB Output is correct
12 Correct 20 ms 35540 KB Output is correct
13 Correct 19 ms 35540 KB Output is correct
14 Correct 18 ms 35572 KB Output is correct
15 Correct 19 ms 35624 KB Output is correct
16 Correct 20 ms 35620 KB Output is correct
17 Correct 18 ms 35540 KB Output is correct
18 Correct 19 ms 35540 KB Output is correct
19 Correct 19 ms 35576 KB Output is correct
20 Correct 19 ms 35560 KB Output is correct
21 Correct 18 ms 35576 KB Output is correct
22 Correct 19 ms 35616 KB Output is correct
23 Correct 20 ms 35568 KB Output is correct
24 Correct 22 ms 35540 KB Output is correct
25 Correct 19 ms 35628 KB Output is correct
26 Correct 19 ms 35568 KB Output is correct
27 Correct 18 ms 35572 KB Output is correct
28 Correct 18 ms 35568 KB Output is correct
29 Correct 18 ms 35532 KB Output is correct
30 Correct 19 ms 35576 KB Output is correct
31 Execution timed out 5104 ms 47908 KB Time limit exceeded
32 Halted 0 ms 0 KB -