Submission #104122

#	Time	Username	Problem	Language	Result	Execution time	Memory
104122		dimash241	New Home (APIO18_new_home)	C++17	45 / 100	3235 ms	169104 KiB

new_home

# include <stdio.h>
# include <bits/stdc++.h>


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (int i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (int i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;
inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; } 
inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, q, k;
int x[N], t[N], a[N], b[N];
int l[N], y[N];
int ans[N];
vector < int > pp;
map < int, int > M;

int get(int x) {
    auto it = M.lower_bound(x);
    int m = 0;
    if (it != M.end()) m = max(m,it->second-(it->first-x));
    if (it != M.begin()) it--,m = max(m,it->second-(x-it->first));
    return m;
}
void ins(int x,int h) {
    if (get(x) >= h) return ;
    auto it = M.lower_bound(x);
    while (it != M.end()) {
        if (it->second > h-(it->first-x)) break;
        else it = M.erase(it);
    }
    M[x] = h;
    it = M.find(x);
    while (1) {
        if (it == M.begin()) break;
        it--;
        if (it->second > h-(x-it->first)) break;
        else it = M.erase(it);
    }
}

inline void solve () {
	for (int i = 1; i <= n; i ++)
		pp.pb(a[i]), pp.pb(b[i]);
	for (int i = 1; i <= q; i ++) {
		pp.pb(y[i]);
	}
	sort(every(pp));
	pp.resize(unique(every(pp)) - pp.begin());
	vector < vector < pair < int, int > > > add(pp.size() + 2);
	vector < vector < pair < int, int > > > del(pp.size() + 2);
	vector < vector < pair < int, int > > > query(pp.size() + 2);
	multiset < int > bl[k + 1];
	for (int i = 1; i <= k; i ++)
		bl[i].clear();
	for (int i = 1; i <= n; i ++) {
		a[i] = lower_bound(every(pp), a[i]) - pp.begin();
		b[i] = lower_bound(every(pp), b[i]) - pp.begin();
		add[a[i]].pb(mp(x[i], t[i]));
		del[b[i]].pb(mp(x[i], t[i]));
	}

	for (int i = 1; i <= q; i ++) {
		y[i] = lower_bound(every(pp), y[i]) - pp.begin();
		query[y[i]].pb(mp(l[i], i));
	}

	for (int vv = 0; vv < pp.size(); vv ++) {

		for (auto it : add[vv]) bl[it.S].insert(it.F);

		for (auto q : query[vv]) {
			int res = 0;
			for (int w = 1; w <= k; w ++) {
				if (bl[w].empty()) {
					res = -1;
					break;
				}

				int cur = inf;
				auto l = bl[w].upper_bound(q.F);
				if (l != bl[w].end()) {
					cur = min(cur, *l - q.F); 
				}
				if (l != bl[w].begin()) {
					--l;
					cur = min(cur, q.F - *l);
				}
		//		cout << cur << ' ' << w << '\n';
				res = max(res, cur);
			}
			ans[q.S] = res;
		}

		for (auto it : del[vv]) bl[it.S].erase(bl[it.S].find(it.F));
	}
	for (int i = 1; i <= q; ++i) {
		if (ans[i] > 1e8) ans[i] = -1;
		printf("%d\n", ans[i]);
	}
}
vector < pair < int, int > > add[N], del[N], query[N];
multiset < int > bl[N];

int main () {
	scanf("%d%d%d", &n, &k, &q);
    for (int i = 1; i <= n; ++i) {
    	scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
    }
    for (int i = 1; i <= q; ++i) {
    	scanf("%d%d", &l[i], &y[i]);
    }
    if (n <= 6e4 && k <= 400) {
    	solve();
    	exit(0);
    }
    
    for (int i = 1; i <= n; ++i)
		pp.pb(a[i]), pp.pb(b[i]);
	for (int i = 1; i <= q; ++i) {
		pp.pb(y[i]);
	}
	sort(every(pp));
	pp.resize(unique(every(pp)) - pp.begin());
	for (int i = 1; i <= n; i ++) {
		a[i] = lower_bound(every(pp), a[i]) - pp.begin();
		b[i] = lower_bound(every(pp), b[i]) - pp.begin();
		add[a[i]].pb(mp(x[i], t[i]));
		del[b[i]].pb(mp(x[i], t[i]));
	}

	for (int i = 1; i <= q; i ++) {
		y[i] = lower_bound(every(pp), y[i]) - pp.begin();
		query[y[i]].pb(mp(l[i], i));
	}
	
	bool f = 0;
	for (auto it : add[0]) bl[it.S].insert(it.F); 
    for (int j = 1; j <= k; ++j) {
                bl[j].insert(-3e8);
                bl[j].insert(3e8);
                for (auto it = ++bl[j].begin(); it != bl[j].end(); it++) {
               		auto it2 = it;
                    it2 --;
                    ins(*it + *it2,*it - *it2);
           		}
    }    
    for (int i = 0; i < pp.size(); ++i) {
    	
      	for (auto it : query[i])
      		ans[it.S] = get(2 * it.F) / 2;
      	for (auto id : del[i]) {
        	int p = id.S;
            auto it = bl[p].find(id.F);
            auto it2 = it;
            it ++, it2 --;
            ins(*it + *it2,*it - *it2);
            bl[p].erase(bl[p].find(id.F));
                
    	}
    }
    for (int i = 1; i <= q; ++i) {
		if (ans[i] > 1e8) ans[i] = -1;
		printf("%d\n", ans[i]);
	}
    return Accepted;
}

// B...a D....

Compilation message (stderr)

new_home.cpp: In function 'void solve()':
new_home.cpp:100:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int vv = 0; vv < pp.size(); vv ++) {
                   ~~~^~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:180:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < pp.size(); ++i) {
                     ~~^~~~~~~~~~~
new_home.cpp:169:7: warning: unused variable 'f' [-Wunused-variable]
  bool f = 0;
       ^
new_home.cpp:138:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:140:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:143:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d", &l[i], &y[i]);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20