QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#298112 | #4629. Longest Increasing Subsequence | defyers# | TL | 0ms | 0kb | C++17 | 1.9kb | 2024-01-05 17:52:26 | 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