TLE 30pts 求调
查看原帖
TLE 30pts 求调
781159
Lovely_Elaina楼主2024/11/27 22:46

我是傻逼,但是怎么改啊 /ll

#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
const int N = 1e5+5;
const int T = 5e4+5;
const int t = 5e4;
// const int t = 15;
const double eps = 1e-9;
const int INF = 2e9;

struct line{
    double s; // 起始值
    double p; // 斜率
}l[N];

struct node{
	int k; // 编号
	double y; // 高度
};

int s[T<<2]; // 存编号
int cntProject;

inline int cmp(double x,double y){	
	if(x - y == eps) return -1;
	return x - y > eps ? 1 : 0;
}

inline double cal(int k,int x){
    return l[k].s + (x-1)*l[k].p;
}

// inline void update(int k,int l,int r,int u){
//     int &v = s[k],mid = l + r >> 1;
// 	int res = cmp(cal(u,mid),cal(v,mid));
//     // cout << res << endl;
// 	if(res == 1 || res == -1 && u < v) swap(u,v);
// 	int resL = cmp(cal(u,l),cal(v,l)),resR = cmp(cal(u,r),cal(v,r));
// 	if(resL == 1 || resL == -1 && u < v) update(k<<1,l,mid,u);
// 	if(resR == 1 || resR == -1 && u < v) update(k<<1|1,mid+1,r,u);
// }

inline void update(int k,int l,int r,int u){
    int mid = l + r >> 1,v = s[k];
	int res = cmp(cal(u,mid),cal(s[k],mid));
    // cout << res << endl;
	if(res == 1 || res == -1 && u < s[k]) s[k] = u;
    if(l == r) return ;
	int resL = cmp(cal(u,l),cal(v,l)),resR = cmp(cal(u,r),cal(v,r));
	// if(resL == 1 || resL == -1 && u < v) update(k<<1,l,mid,u);
	// if(resR == 1 || resR == -1 && u < v) update(k<<1|1,mid+1,r,u);
    update(k<<1,l,mid,u);
	update(k<<1|1,mid+1,r,u);
}

inline void add(double s,double p){
    l[++cntProject] = (line){s,p};
    update(1,1,t,cntProject);
}

inline int query(int k,int l,int r,int d){
    if(l == r) return s[k];
    
    int mid = l + r >> 1,res;
    if(d <= mid) res = query(k<<1,l,mid,d);
    if(d > mid) res = query(k<<1|1,mid+1,r,d);
    
    return res;
}

inline void print(int k,int l,int r){
    if(l == r){
        cout << s[k] << " ";
        cout << cal(s[k],l) << " - ";
        return ;
    }
    
    int mid = l + r >> 1;
    print(k<<1,l,mid);
    print(k<<1|1,mid+1,r);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // freopen("app.in","r",stdin);
    
    l[0] = (line){-INF,0};
    
    int M,day;
    double s,p;
    string q;
    
    cin >> M;
    while(M--){
        cin >> q;
        if(q == "Query"){
            cin >> day;
            if(!cntProject || cal(query(1,1,t,day),day) < 0){
                cout << 0 << endl;
                continue;
            }
            // cout << query(1,1,t,day) << " ";
            cout << (int)cal(query(1,1,t,day),day)/100 << endl;
        }else if(q == "Project"){
            cin >> s >> p;
            add(s,p);
        }
//        cout << q << q << q << endl;
    }
    
    // print(1,1,t);
    // for(int i = 1; i <= cntProject; i++){
    //     cout << endl;
    //     for(int j = 1; j <= t; j++){
    //         cout << j << " ";
    //         cout << cal(i,j) << " - ";
    //     }
    // }
    return 0;
}
2024/11/27 22:46
加载中...