QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#298112#4629. Longest Increasing Subsequencedefyers#TL 0ms0kbC++171.9kb2024-01-05 17:52:262024-01-05 17:52:26

Judging History

你现在查看的是最新测评结果

  • [2024-01-05 17:52:26]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-01-05 17:52:26]
  • 提交

answer

#include "bits/stdc++.h"

#pragma GCC optimize("Ofast")
#pragma GCC targetr("avx2")

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define int long long

const int N = 2e5 + 11;
const int V = 1e6 + 11;

int v[N], l[N], r[N];

struct node{
	int w, s;
};

int n, m; 

struct BIT{
	int bit[V], sum = 0;
	void add(int p, int v){ sum += v; for(int i = p; i < V; i += i & -i) bit[i] += v; }
	int qry(int p){ int ret = 0; for(int i = p; i; i -= i & -i) ret += bit[i]; return ret; }
} bit0, bit1;

void add(int profit, int quantity){
	bit0.add(profit, quantity);
	bit1.add(profit, quantity * profit);
}

void query(){
	int p = 0;
	int P = 0, Q = 1;
	for(int j = 19; j >= 0; j--){
		if(p + (1 << j) < V){
			int s0 = bit0.sum - bit0.qry(p + (1 << j) - 1);
			int s1 = bit1.sum - bit1.qry(p + (1 << j) - 1);
			// cout << s1 << ' ' << (s0 + r[0]) << ' ' << p + (1 << j) << '\n';
			if(s1 != 0 && s1 <= (s0 + r[0]) * (p + (1 << j))){
				p += (1 << j);
				P = s1; Q = s0 + r[0];
			}
		}
	}

	int g = gcd(P, Q);
	P /= g; Q /= g;
	cout << P << '/' << Q << '\n';
}

void solve(int TC) {
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> v[i];
	}
	for(int i = 0; i <= n; i++){
		cin >> l[i];
	}
	for(int i = 0; i <= n; i++){
		cin >> r[i];
	}

	for(int i = 1; i <= n; i++){
		add(v[i], l[i]);
	}
	query();
	for(int i = 0; i < m; i++){
		int t; cin >> t;
		if(t == 1){
			int x, y, z; cin >> x >> y >> z;
			if(x != 0) add(v[x], -l[x]);
			l[x] = y, r[x] = z;
			if(x != 0) add(v[x], l[x]);
		}else{
			int x, y; cin >> x >> y;
			assert(x >= 1);
			add(v[x], -l[x]);
			v[x] = y;
			add(v[x], l[x]);
		}
		query();
	}
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

7
7 41 53 58 75 78 81

output:


result: