NEERC2014 Eastern subregional

时间:2023-11-23 12:50:50

\

先把furthur的超碉线段树粘过来

 //#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<climits>
using namespace std;
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("in.txt","r",stdin)
#define WE freopen("matrix.out","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
typedef long long ll;
typedef unsigned long long ull;
typedef long double LD; const int maxn=; int n; struct Node {
int money;
int day,month;
int hour,mini;
int no;
} a[maxn]; bool cmp(Node x, Node y) {
if(x.month!=y.month)return x.month<y.month;
if(x.day!=y.day)return x.day<y.day;
if(x.hour!=y.hour)return x.hour<y.hour;
return x.mini<y.mini;
} bool cmp2(int x,int y) {
return cmp(a[x],a[y]);
} int c[maxn];
ll mi[maxn << ], cov[maxn << ];
void pushDown(int rt){
if(cov[rt]){
cov[rt << ] += cov[rt];
cov[rt << | ] += cov[rt];
mi[rt << ] += cov[rt];
mi[rt << | ] += cov[rt];
cov[rt] = ;
}
}
void pushUp(int rt){
mi[rt] = min(mi[rt << ], mi[rt << | ]);
}
void Update(int L, int R, int val, int l, int r, int rt){
if(L <= l && R >= r){
mi[rt] += val;
cov[rt] += val;
return;
}
pushDown(rt);
int m = (l + r) >> ;
if(L <= m) Update(L, R, val, lson);
if(R > m) Update(L, R, val, rson);
pushUp(rt);
}
void farm() {
int i,j,k;
REP(i,n)c[i]=i;
sort(c,c+n,cmp2);
REP(i,n)a[c[i]].no=i+;
///a[i].no = 1~n
mz(mi);
mz(cov);
for(int i=; i<n; i++){
//printf("%d %d\n", a[i].no, a[i].money);
Update(a[i].no, n, a[i].money, , n, );
ll ans = min(mi[], 0LL);
printf("%I64d\n",ans);
}
} int main() {
//RE;
int i;
while(scanf("%d",&n)!=EOF) {
REP(i,n)scanf(" %d%d.%d%d:%d",&a[i].money , &a[i].day , &a[i].month , &a[i].hour, &a[i].mini);
farm();
}
return ;
}