Submission #771608

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
771608	2023-07-03T07:19:45 Z	Sam_a17	New Home (APIO18_new_home)	C++17	10 / 100	1780 ms	223160 KB

new_home

#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], qq[3 * N];
map<int, vector<pair<int, int>>> upds;
map<int, vector<int>> ups;
int n, k, q, answ[N];
int val[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});
  }

  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';
  }
}
 
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:100:7: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
  100 |   int flag = 1;
      |       ^~~~
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
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	28500 KB	Output is correct
2	Incorrect	15 ms	28512 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	28500 KB	Output is correct
2	Incorrect	15 ms	28512 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1693 ms	203244 KB	Output is correct
2	Correct	1060 ms	221548 KB	Output is correct
3	Correct	1192 ms	190380 KB	Output is correct
4	Correct	1620 ms	212116 KB	Output is correct
5	Correct	1039 ms	221076 KB	Output is correct
6	Correct	1056 ms	221468 KB	Output is correct
7	Correct	1061 ms	190328 KB	Output is correct
8	Correct	1635 ms	211900 KB	Output is correct
9	Correct	1686 ms	220416 KB	Output is correct
10	Correct	1406 ms	223160 KB	Output is correct
11	Correct	1051 ms	219056 KB	Output is correct
12	Correct	1234 ms	221972 KB	Output is correct