oj.uz

답안 #571762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571762 2022-06-02T16:40:19 Z gs14004 Fish 2 (JOI22_fish2) C++17
0 / 100
 4000 ms 6908 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int MAXN = 100005;

lint a[MAXN];

struct node{
	int s, e, cost;
	bool operator<(const node &nd)const{
		return pi(s, -e) < pi(nd.s, -nd.e);
	}
};

struct bit{
	lint tree[MAXN];
	void add(int x, lint v){
		for(int i = x; i < MAXN; i += i & -i) tree[i] += v;
	}
	lint query(int x){
		lint ret = 0;
		for(int i = x; i; i -= i & -i) ret += tree[i];
		return ret;
	}
	lint query(int s, int e){
		if(s > e) return 0;
		return query(e) - query(s - 1);
	}
}bit, subs;

int n;
set<node> st;

void turnOn(int x, int p){
	int l = x, r = x;
	vector<node> v;
	while(l > 1 && r < n){
		lint curSum = bit.query(l, r);
		if(curSum < min(a[l-1], a[r+1])){
			v.push_back({l,r, -1});
			if(a[l-1] < a[r+1]) l--;
			else r++;
		}
		curSum = bit.query(l, r);
		int leftClosest = 0, rightClosest = n + 1;
		for(int i = l - 1; i > 0; i--){
			if(a[i] > curSum){
				leftClosest = i;
				break;
			}
		}
		for(int i = r + 1; i <= n; i++){
			if(a[i] > curSum){
				rightClosest = i;
				break;
			}
		}
		l = leftClosest + 1;
		r = rightClosest - 1;
	}
	for(auto &x : v){
		if(p == 1){
			auto it = st.lower_bound({x.s, x.e, -1});
			if(it != st.end() && it->s == x.s && it->e == x.e){
				subs.add(it->s - 1, -it->cost);
				st.erase(it);
			}
			int sum = subs.query(x.s - 1, x.e);
			subs.add(x.s - 1, x.e - x.s + 1 - sum);
			st.insert({x.s, x.e, x.e - x.s + 1 - sum});
	//		cout << "Add interval " << x.s << " " << x.e << " " << x.e - x.s + 1 - sum << endl;
		}
		else{
			auto it = st.lower_bound({x.s, x.e, -1});
			if(it != st.end() && it->s == x.s && it->e == x.e){
	//			cout << "Erase interval " << x.s << " " << x.e << " " << it->cost << endl;
				subs.add(it->s - 1, -it->cost);
				st.erase(it);
			}
		}
	}
}

void add(int x, int v){
			turnOn(x-1, -1);
			turnOn(x, -1);
			turnOn(x+1, -1);
			bit.add(x, v);
			a[x] += v;
			turnOn(x-1, +1);
			turnOn(x, +1);
			turnOn(x+1, +1);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	a[1] = a[n + 2] = 1e15;
	for(int i = 2; i <= n + 1; i++){
		cin >> a[i];
	}
	n += 2;
	for(int i = 1; i <= n; i++){
		bit.add(i, a[i]);
	}
	for(int i = 2; i <= n - 1; i++){
		turnOn(i, +1);
	}
	int q; cin >> q;
	while(q--){
		int t, x, y; cin >> t >> x >> y;
		if(t == 1){
			x++;
			add(x, y - a[x]);
		}
		else{
			x++; y++;
			int sx = x, sy = y;
			add(x - 1, 2e9);
			add(y + 1, 2e9);
			for(int i = x; i <= y; i++){
				if(bit.query(x, i - 1) < a[i]) sx = i;
			}
			for(int i = y; i >= x; i--){
				if(bit.query(i + 1, y) < a[i]) sy = i;
			}
			if(sx > sy){
				cout << "0\n";
				continue;
			}
			cout << sy - sx + 1 - subs.query(sx, sy - 1) << "\n";
			add(x - 1, -2e9);
			add(y + 1, -2e9);
		}
	}
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Incorrect 12 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 4075 ms 6908 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Incorrect 12 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 4075 ms 6908 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 4075 ms 6908 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Incorrect 12 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -