首页 > 代码库 > URAL 2014 Zhenya moves from parents
URAL 2014 Zhenya moves from parents
2014. Zhenya moves from parents
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Zhenya moved from his parents’ home to study in other city. He didn’t take any cash with him, he only took his father’s credit card with zero balance on it. Zhenya succeeds in studies at the University and sometimes makes a little money on the side as a Maths tutor. As he makes his own money he spends only it, and when it is over he uses the credit card. Every time he gets or spends money, he sends a letter to his father, where he puts the following two things.
- The date when it took place
- The sum of earned or spent money
Every time receiving a letter from Zhenya, his father calculates the debt on the credit card at the moment. But here a problem arises. The point is that Russian Post delivers letters in an order different to the one they were sent in.
For example, in the first Zhenya’s letter the father read that on September 10 Zhenya spent one thousand rubles. He thought that his son had used the credit card, and now the debt is one thousand rubles. However the next day came a letter with the information that on September 9 Zhenya earned five hundred rubles. It means that half of the money he spent on September 10 was his own, and the debt on the credit card is just five hundred rubles.
Help Zhenya’s father with his account management.
Input
The first line contains an integer n which is the number of Zhenya’s letters (1 ≤ n ≤ 100 000). These letters are listed in the nextn lines. Description of each letter consists of the amount of money Zhenya spent or earned (in the form -c or +c accordingly, where c is an integer, 1 ≤ c ≤ 50 000) followed by both date and time when it took place (in the form of dd.MM hh:mm). All dates belong to the same year, which is not leap (i. e. there are 365 days in it). Any two letters contain either different dates or different time. The letters are listed in the order the father received them.
Output
After each received letter output what Zhenya’s father thinks the amount of the debt on the credit card is.
Sample
| input | output |
|---|---|
5-1000 10.09 21:00+500 09.09 14:00+1000 02.09 00:00-1000 17.09 21:00+500 18.09 13:00 | -1000-5000-500-500
|
这个题目确实一条有趣的题目。
而当孩子现金不足的时候，孩子会使用信用卡 。
然后每次孩子挣到钱或者花了钱都会寄信告诉父亲。
给出一个值 x ,还有时间 t 。
表示孩子在 t 时间的时候挣了 x 元 （ x 为 正 ）， 或者花了x元 。
但是信件发送的时间与到达的时间并非一致 。
而父亲每次收到信件想估计（用当前有的信息）信用卡现在的负债多少。
#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 100010;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define lr rt<<1#define rr rt<<1|1#define root 1,n+100,1int n;LL date[N<<2] , lazy[N<<2] ;vector<int>tt;int t[N];LL v[N];void build( int l , int r , int rt ){ date[rt] = lazy[rt] = 0 ; if( l == r ) return ; int mid = (l+r) >> 1; build( lson ) ; build( rson ) ;}void Up(int rt){ date[rt] = min( date[lr] , date[rr]); }void Down( int rt ){ if( lazy[rt] ){ lazy[lr] += lazy[rt], lazy[rr]+=lazy[rt]; date[lr] += lazy[rt], date[rr] += lazy[rt]; lazy[rt] = 0 ; }}void update( int l , int r , int rt , int L , int R , LL val ){ if( L <= l && r <= R ){ lazy[rt] += val , date[rt] += val; return ; } Down(rt); int mid = (l + r) >> 1; if( L <= mid ) update(lson,L,R,val); if( R > mid ) update(rson,L,R,val); Up(rt);}int main(){ #ifdef LOCAL freopen("in","r",stdin); #endif int mon , day , hour , min ; while( scanf("%d",&n ) != EOF ){ tt.clear(); build(root); for( int i = 0 ; i < n ; ++i ){ scanf("%lld%d.%d%d:%d",&v[i],&day,&mon,&hour,&min); t[i] = ( ( mon * 31 + day ) * 24 + hour ) * 60 + min ; tt.push_back(t[i]); } sort( tt.begin() , tt.end() ); for( int i = 0 ; i < n ; ++i ) { int pos = lower_bound( tt.begin() , tt.end(), t[i] ) - tt.begin() + 1 ; update( root , pos , n , v[i] ) ; printf("%I64d\n",( date[1] >= 0 ? 0 : date[1]) ) ; } } return 0;}
URAL 2014 Zhenya moves from parents
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。