Submission #210874

#	Time	Username	Problem	Language	Result	Execution time	Memory
210874		jtnydv25	Two Antennas (JOI19_antennas)	C++14	22 / 100	594 ms	31352 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	for(int i = 0;i < (int)v.size(); i++){
		if(i)os<<", ";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int N = 200005;
const int DEFAULT_MIN = 1<<30;
const int DEFAULT_MAX = -DEFAULT_MIN;
// mt19937_64 for 64 bit
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int getRand(int x, int y){
	return uniform_int_distribution<int>(x, y)(rng);
}
int cnt = 0;
struct Node{
	int key, value, lazy, lazy_min, lazy_max, itself_min, itself_max, height, mnH, mxH, maxDiff;
	Node* lft, *rgt;
	Node(){
		lazy = 0;
		lft = rgt = NULL;
		lazy_min = itself_min = DEFAULT_MIN;
		lazy_max = itself_max = DEFAULT_MAX;
		maxDiff = -1;
	}
	Node(int value, int height) : value(value), lazy(0), height(height), mnH(height), mxH(height){
		key = getRand(1, 1 << 29);
		maxDiff = -1;
		lft = rgt = NULL;
		lazy_min = itself_min = DEFAULT_MIN;
		lazy_max = itself_max = DEFAULT_MAX;
	}
	void push(){
		if(!lazy) return;
		itself_min = min(itself_min, lazy_min);
		itself_max = max(itself_max, lazy_max);
		maxDiff = max(maxDiff, lazy_max - mnH);
		maxDiff = max(maxDiff, mxH - lazy_min);
		if(lft){
			lft->lazy_min = min(lft->lazy_min, lazy_min);
			lft->lazy_max = max(lft->lazy_max, lazy_max);
			lft->lazy = 1;
		}
		if(rgt){
			rgt->lazy_min = min(rgt->lazy_min, lazy_min);
			rgt->lazy_max = max(rgt->lazy_max, lazy_max);
			rgt->lazy = 1;
		}
		lazy_min = DEFAULT_MIN;
		lazy_max = DEFAULT_MAX;
		lazy = 0;
	}
	void upd(){
		int V = max(-1, max(height - itself_min, itself_max - height));
		maxDiff = max({V, lft? lft-> maxDiff : -1, rgt ? rgt -> maxDiff : -1});
		mnH = min({height, lft ? lft->mnH : DEFAULT_MIN, rgt ? rgt->mnH : DEFAULT_MIN});
		mxH = max({height, lft ? lft->mxH : DEFAULT_MAX, rgt ? rgt->mxH : DEFAULT_MAX});
	}
};


struct treap{
	Node* root;
	treap(){root = NULL;}
	Node* merge(Node* A, Node* B){
		if(!A && !B) return NULL;
		if(!A){
			B->push();
			return B;
		}
		if(!B){
			A->push();
			return A;
		}
		if(A->key > B->key){
			A->push();
			A->rgt = merge(A->rgt, B);
			A->upd();
			return A;
		}else {
			B->push();
			B->lft = merge(A, B->lft);
			B->upd();
			return B;
		}
	}

	// <= v, > v
	pair<Node*, Node*> split(Node* A, int v){
		if(!A) return {NULL, NULL};
		A->push();
		if(A->value <= v){
			pair<Node*, Node*> BC = split(A->rgt, v);
			A->rgt = BC.F;
			if(A->lft) A->lft->push();
			A->upd();
			return {A, BC.S};
		} else{
			pair<Node*, Node*> BC = split(A->lft, v);
			A->lft = BC.S;
			if(A->rgt) A->rgt->push();
			A->upd();
			return {BC.F, A};
		}
	}

	void insert(int v, int h){
		Node* node = new Node(v, h);
		if(!root){
			root = node;
			return;
		}
		pair<Node*, Node*> BC = split(root, v);
		Node* lft = BC.F, * rgt = BC.S;
		root = merge(merge(lft, node), rgt);
	}

	void update(int l, int r, int v){
		pair<Node*, Node*> temp = split(root, l - 1);
		Node* A = temp.F;
		pair<Node*, Node*> BC = split(temp.S, r);
		Node* B = BC.F, *C = BC.S;
		if(B){
			B->lazy_min = B->lazy_max = v;
			B->lazy = 1;
		}
		root = merge(A, merge(B, C));
	}

	int get(int l, int r){
		pair<Node*, Node*> temp = split(root, l - 1);
		Node* A = temp.F;
		pair<Node*, Node*> BC = split(temp.S, r);
		Node* B = BC.F, *C = BC.S;
		int ret = B ? B->maxDiff : -1;
		root = merge(A, merge(B, C));
		return ret;
	}

	int erase(int x){
		pair<Node*, Node*> temp = split(root, x - 1);
		Node* A = temp.F;
		pair<Node*, Node*> BC = split(temp.S, x);
		int ret = -1;
		Node* to_remove = BC.F;
		if(to_remove){
			ret = to_remove -> maxDiff;
			delete to_remove;
		}
		root = merge(A, BC.S);
		return ret;
	}

	void traverse(Node* rt){
		cerr<<"[ ";
		function<void(Node*)> go = [&](Node* nd){
			if(!nd) return;
			nd->push();
			go(nd->lft);
			cerr<<"("<<nd->value << ", " << nd->lazy_min << ")" << " ";
			go(nd->rgt);
		};
		go(rt);
		cerr<<"]" << endl;
	}
};

struct segtree{
	int n;
	vector<int> t;
	int def;

	segtree(int n, int def = -1) : n(n), def(def){
		t.resize(2 * n, def);
	}

	void modify(int p, int value) { // modify a[p] = value
		for (t[p += n] = value; p >>= 1; ) t[p] = max(t[p<<1], t[p<<1|1]);
	}

	int query(int l, int r) {  // compute on interval [l, r]
    r++;
		int resl = def, resr = def;
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (l&1) resl = max(resl, t[l++]);
			if (r&1) resr = max(t[--r], resr);
		}
		return max(resl, resr);
	}
};

vector<int> queries[N];
int L[N], R[N], A[N], B[N], H[N], ans[N];
vector<int> insertions[N], removals[N];

int main(){
	treap T;
	int n, q; sd(n);
	memset(ans, -1, sizeof ans);
	for(int i = 1; i <= n; i++){
		sd(H[i]); sd(A[i]); sd(B[i]);
		if(i + A[i] <= n) insertions[i + A[i]].push_back(i);
		if(i + B[i] <= n) removals[i + B[i]].push_back(i);
	}

	sd(q);
	for(int i = 1; i <= q; i++){
		sd(L[i]); sd(R[i]);
		queries[R[i]].push_back(i);
	}
	segtree st(n + 1);
	for(int j = 1; j <= n; j++){
		int l = max(1, j - B[j]);
		int r = j - A[j];
		for(int i : insertions[j]){
			T.insert(i, H[i]);
		}

		if(r >= l){
			T.update(l, r, H[j]);
		}

		for(int ind : queries[j]){
			int X = T.get(L[ind], R[ind]);
			int Y = st.query(L[ind], R[ind]);
			ans[ind] = max(X, Y);
		}
		for(int i : removals[j]){
			st.modify(i, T.erase(i));
		}
	}

	for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}	

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
antennas.cpp:242:12: note: in expansion of macro 'sd'
  int n, q; sd(n);
            ^~
antennas.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
antennas.cpp:245:3: note: in expansion of macro 'sd'
   sd(H[i]); sd(A[i]); sd(B[i]);
   ^~
antennas.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
antennas.cpp:245:13: note: in expansion of macro 'sd'
   sd(H[i]); sd(A[i]); sd(B[i]);
             ^~
antennas.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
antennas.cpp:245:23: note: in expansion of macro 'sd'
   sd(H[i]); sd(A[i]); sd(B[i]);
                       ^~
antennas.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
antennas.cpp:250:2: note: in expansion of macro 'sd'
  sd(q);
  ^~
antennas.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
antennas.cpp:252:3: note: in expansion of macro 'sd'
   sd(L[i]); sd(R[i]);
   ^~
antennas.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
antennas.cpp:252:13: note: in expansion of macro 'sd'
   sd(L[i]); sd(R[i]);
             ^~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65