正文

ural2014zhenyamovesfromparents线段树

author  author  2022-09-07  734

关键词：

线段树，前缀和最小

Zhenya moves from parents

Time Limit: 1000MS

Memory Limit: 65536KB

64bit IO Format: %I64d & %I64u

Submit Status

Description

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 next n 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

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 -500 0 -500 -500

Source

Problem Author: Nick Burlakov (prepared by Olga Soboleva)
Problem Source: NEERC 2014, Eastern subregional contest

Submit Status

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long int LL;

const int maxn=110000;

int n;
LL money[maxn];
LL Time[maxn],T[maxn];

LL add[maxn<<2],mx[maxn<<2];

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

void build(int l,int r,int rt)
{
  add[rt]=0,mx[rt]=0;
  if(l==r) return ;
  int m=(l+r)/2;
  build(lson); build(rson);
}

void upd_add(int rt)
{
  if(add[rt])
    {
      mx[rt<<1]+=add[rt];
      mx[rt<<1|1]+=add[rt];
      add[rt<<1]+=add[rt];
      add[rt<<1|1]+=add[rt];
      add[rt]=0;
    }
}

void push_down(int rt)
{
  upd_add(rt);
}

void push_up(int rt)
{
  mx[rt]=min(mx[rt<<1],mx[rt<<1|1]);
}

void update(int L,int R,int V,int l,int r,int rt)
{
  if(L<=l&&r<=R)
    {
      add[rt]+=V;
      mx[rt]+=V;
      return ;
    }
  push_down(rt);
  int m=(l+r)/2;
  if(L<=m) update(L,R,V,lson);
  if(R>m) update(L,R,V,rson);
  push_up(rt);
}

int main()
{
  scanf("%d",&n);
  getchar();
  for(int i=0;i<n;i++)
    {
      char op;
      LL mo;
      int day,mouth,hh,mm;
      scanf("%c%I64d %d.%d %d:%d",&op,&mo,&day,&mouth,&hh,&mm);
      money[i]=mo;
      if(op==‘-‘) money[i]*=-1;
      Time[i]=1LL*(mouth*31+day)*24*60+hh*60+mm;
      T[i]=Time[i];
    }
  sort(T,T+n);
  int m=unique(T,T+n)-T;
  build(1,n,1);
  for(int i=0;i<n;i++)
    {
      int id=lower_bound(T,T+m,Time[i])-T+1;
      update(id,n,money[i],1,n,1);
      printf("%I64d
",mx[1]>=0?0:mx[1]);
    }
  return 0;
}

ural-1901spaceelevators

题目：NowadaysspaceshipsareneverlaunchedfromtheEarth‘ssurface.ThereisahugespaceportplacedinthegeostationaryorbitandconnectedtotheEarthwithcarbonnanotubecables.Peopleandcargoaredeliveredtotheorbitbyelevat 查看详情

ural2089experiencedcoachtwosat

DescriptionMishatrainsseveralACMteamsattheuniversity.Heisanexperiencedcoach,andhedoesnotunderestimatethemeaningoffriendlyandcollaborativeatmosphereduringtrainingsessions.Itusedtobethatway,butoneofthet 查看详情

ural2020trafficjaminflowertown

2020.TrafficJaminFlowerTownTimelimit:1.0secondMemorylimit:64MBHavingreturnedfromSunCity,Dunnotoldallhisfriendsthateveryshortymayhaveapersonalautomobile.Immediatelyafterthatsomanycitizenstookafancyofbe 查看详情

ural1424minibus

MinibusTimelimit:1.0secondMemorylimit:64MBBackgroundMinibusdriverSergeyA.Greedsonhasbecometotallyfamousforhisphenomenalgreediness.Heclaimedtimeandagainthatheheldhimselfinreadinesstothrottlehisbrothera 查看详情

ural1855tradeguildsoferathia

TradeGuildsofErathiaTimelimit:2.0secondMemorylimit:64MBThecontinentofAntagarichwascolonizedslowly.LongagoitsnorthernpartwasinhabitedbytheelvesofAvlee.Later,thehotsoutherndesertofBracadawasoccupiedbyth 查看详情

ural2016magicandscience

2016.MagicandScienceTimelimit:1.0secondMemorylimit:64MBScientistswhospecializeinwitchcrafthaverecentlydiscoveredanewelementaryparticlecalledamagion.Studyingthelawsofmagions’movement,agroupofthre 查看详情

ural2021scarilyinteresting!

2021.Scarilyinteresting!Timelimit:1.0secondMemorylimit:64MBThisyearatMonstersUniversityitisdecidedtoarrangeScareGames.AttheGamesallcampusgathersatthestadiumstands,andtheScareprogramstudentsdivideintot 查看详情

[ural1519]formula1

[URAL1519]Formula1试题描述Regardlessofthefact,thatVologdacouldnotgetrightstoholdtheWinterOlympicgamesof20**,itiswell-known,thatthecitywillconductoneoftheFormula1events.Surely,forsuchanimportantthinganewra 查看详情

ural1118.nontrivialnumbers

1118.NontrivialNumbersTimelimit:2.0secondMemorylimit:64MB SpecialistsofSKBKonturhavedevelopedauniquecryptographicalgorithmforneedsofinformationprotectionwhiletransmittingdataovertheInternet.Thema 查看详情

ural2015zhenyamovesfromthedormitory

2015.ZhenyamovesfromthedormitoryTimelimit:1.0secondMemorylimit:64MBAftermovingfromhisparents’placeZhenyahasbeenlivingintheUniversitydormitoryforamonth.However,hegotprettytiredofthecurfewtimeandq 查看详情

ural2017bestofabadlot

2017.BestofabadlotTimelimit:1.0secondMemorylimit:64MBAcruiselinerhasn’tmovedawayfromthelandevenforthreemileswhenitbecameapparentthatsomebodyhasdrownedoneofthestewardsintheswimmingpool.Thecaptain 查看详情

ural2012aboutgrishan.

2012.AboutGrishaN.Timelimit:1.0secondMemorylimit:64MBGrishaN.toldhistwoteammatesthathewasgoingtosolveallgivenproblemsatthesubregionalcontest,eveniftheteammateswouldn’tshowupatthecompetition.Thet 查看详情

ural2022ridingatoad

2022.RidingaToadTimelimit:1.0secondMemorylimit:64MBAtribeofleafmenliveintheoldforest.Leafmenareverytinyandfast,that’swhywecan’tnoticethemevenwhentheyareunderourverynose.Leafmenguardthefore 查看详情

ural1196.historyexam（二分）

1196.HistoryExamTimelimit:1.5secondMemorylimit:64MBProfessorofhistorydecidedtosimplifytheexaminationprocess.Attheexam,everystudentshouldwritealistofhistoricdatessheknows(sheshouldwritetheyearsonlyand, 查看详情

ural1224.spiral（规律）

1224.SpiralTimelimit:1.0secondMemorylimit:64MBAbrandnewsapperrobotisabletoneutralizeminesinarectangularregionhavingintegerheightandwidth(NandMrespectively).Beforetherobotbeginsitsworkitisplacednearthe 查看详情

ural2031.overturnednumbers（枚举）

2031.OverturnedNumbersTimelimit:1.0secondMemorylimit:64MBLittlePierrewassurfingtheInternetandcameacrossaninterestingpuzzle:Whatisthenumberunderthecar?IttooksometimebeforePierresolvedthepuzzle,butevent 查看详情

ural1081binarylexicographicsequence（递归）(代码片段)

URAL1081.BinaryLexicographicSequenceTimelimit:0.5secondMemorylimit:64MBDescriptionConsiderallthesequenceswithlength(0<N<44),containingonlytheelements0and1,andnotwoonesareadjacent(110isnotavalids 查看详情

ural1343.fairytale打表

1343.FairyTaleTimelimit:1.0secondMemorylimit:64MB 12monthstosinganddanceinaringtheircelestialdance.Oneafteranothertheyholdathrone.ThefirstisyoungandfierceJanuaryandthelastiselderlyandwiseDecember 查看详情