답안 #771639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
771639	2023-07-03T07:40:13 Z	Sam_a17	새 집 (APIO18_new_home)	C++17	15 / 100	5000 ms	219148 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];
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-