Compensation

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

const int inf=1e8;

int cb[101010];
int vv[101010][2];

vector<pair<int, int> > go[111];
vector<int> arr[111];

int n,m;

void solve(int ttt, vector<pair<int, pair<int, int> > > s){
	for (int i=1;i<=n;i++){
		go[i].clear();
		arr[i].clear();
	}
	for (auto ss:s){
		go[ss.F].push_back(ss.S);
	}
	for (int i=1;i<=n;i++){
		sort(go[i].begin(), go[i].end());
		arr[i].resize(go[i].size());
	}
	for (int i=(int)go[n-1].size()-1;i>=0;i--){
		arr[n-1][i]=go[n-1][i].S;
		if (i+1<(int)go[n-1].size()){
			arr[n-1][i]=min(arr[n-1][i], arr[n-1][i+1]);
		}
	}
	for (int i=n-2;i>=1;i--){
		for (int j=(int)go[i].size()-1;j>=0;j--){
			pair<int, int> asdf={go[i][j].S, 0};
			int id=lower_bound(go[i+1].begin(), go[i+1].end(), asdf)-go[i+1].begin();
			if (id>=(int)go[i+1].size()){
				arr[i][j]=inf;
			}
			else{
				arr[i][j]=arr[i+1][id];
			}
			if (j+1<(int)go[i].size()){
				arr[i][j]=min(arr[i][j], arr[i][j+1]);
			}
		}
	}
	int i2=(int)go[1].size()-1;
	int mv=inf;
	for (int i=90000;i>=0;i--){
		while (i2>=0&&go[1][i2].F>=i){
			mv=min(mv, arr[1][i2]);
			i2--;
		}
		vv[i][ttt]=mv;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	vector<pair<int, pair<int, int> > > s1;
	vector<pair<int, pair<int, int> > > s2;
	for (int i=0;i<m;i++){
		int x,s,t,l;
		cin>>x>>s>>t>>l;
		if (x==1) cb[s]=1;
		s1.push_back({x, {s, t}});
		s2.push_back({x, {s+l, t+l}});
	}
	solve(0, s1);
	solve(1, s2);
	for (int i=0;i<=90000;i++){
		if (cb[i]&&vv[i][0]+1800<=vv[i][1]){
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<"impossible"<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED