Submission #720848

#	Time	Username	Problem	Language	Result	Execution time	Memory
720848		WonderfulWhale	Global Warming (CEOI18_glo)	C++17	48 / 100	589 ms	262144 KiB

glo

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

#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

struct SegTree {
	unsigned int tl, tr;
	int Max = 0;
	SegTree *lc=nullptr, *rc=nullptr;
	SegTree(unsigned int l, unsigned int r) : tl(l), tr(r) {}
	void extend() {
		if(!lc&&tl!=tr) {
			int tm = (tl+tr)/2;
			lc = new SegTree(tl, tm);
			rc = new SegTree(tm+1, tr);
		}
	}
	void update(int x, int val) {
		extend();
		Max = max(Max, val);
		if(lc) {
			if(x <= lc->tr) {
				lc->update(x, val);
			} else {
				rc->update(x, val);
			}
		}
	}
	int query(int l, int r) {
		if(l>r) return 0;
		if(tl==l&&tr==r) return Max;
		extend();
		int tm = (tl+tr)/2;
		return max(lc->query(l, min(r, tm)), rc->query(max(tm+1, l), r));
	}
};

SegTree seg1(0, 1LL<<31), seg2(0, 1LL<<31);

int tab[200009];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, d;
	cin >> n >> d;
	for(int i=0;i<n;i++) {
		cin >> tab[i];
	}
	for(int i=0;i<n;i++) {
		seg2.update(tab[i], 1+seg1.query(0, tab[i]+d-1));
		seg2.update(tab[i], 1+seg2.query(0, tab[i]-1));
		seg1.update(tab[i], 1+seg1.query(0, tab[i]-1));
	}
	cout << seg2.query(0, 1LL<<30) << "\n";
}

Compilation message (stderr)

glo.cpp: In member function 'void SegTree::update(int, int)':
glo.cpp:27:9: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   27 |    if(x <= lc->tr) {
      |       ~~^~~~~~~~~
glo.cpp: In member function 'int SegTree::query(int, int)':
glo.cpp:36:8: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   36 |   if(tl==l&&tr==r) return Max;
      |      ~~^~~
glo.cpp:36:15: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   36 |   if(tl==l&&tr==r) return Max;
      |             ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25