NEERC2014 Eastern subregional

\

 

 

 

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

NEERC2014 Eastern subregional
NEERC2014 Eastern subregional
  1 //#pragma comment(linker, "/STACK:102400,102400")
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<iostream>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<cmath>
  8 #include<map>
  9 #include<set>
 10 #include<stack>
 11 #include<queue>
 12 #include<climits>
 13 using namespace std;
 14 #define mz(array) memset(array, 0, sizeof(array))
 15 #define mf1(array) memset(array, -1, sizeof(array))
 16 #define minf(array) memset(array, 0x3f, sizeof(array))
 17 #define REP(i,n) for(i=0;i<(n);i++)
 18 #define FOR(i,x,n) for(i=(x);i<=(n);i++)
 19 #define FORD(i,x,y) for(i=(x);i>=(y);i--)
 20 #define RD(x) scanf("%d",&x)
 21 #define RD2(x,y) scanf("%d%d",&x,&y)
 22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
 23 #define WN(x) printf("%d\n",x);
 24 #define RE  freopen("in.txt","r",stdin)
 25 #define WE  freopen("matrix.out","w",stdout)
 26 #define mp make_pair
 27 #define pb push_back
 28 #define pf push_front
 29 #define ppf pop_front
 30 #define ppb pop_back
 31 #define lson l, m, rt << 1
 32 #define rson m + 1, r, rt << 1  1
 33 typedef long long ll;
 34 typedef unsigned long long ull;
 35 typedef long double LD;
 36 
 37 const int maxn=;
 38 
 39 int n;
 40 
 41 struct Node {
 42     int money;
 43     int day,month;
 44     int hour,mini;
 45     int no;
 46 } a[maxn];
 47 
 48 bool cmp(Node x, Node y) {
 49     if(x.month!=y.month)return x.month<y.month;
 50     if(x.day!=y.day)return x.day<y.day;
 51     if(x.hour!=y.hour)return x.hour<y.hour;
 52     return x.mini<y.mini;
 53 }
 54 
 55 bool cmp2(int x,int y) {
 56     return cmp(a[x],a[y]);
 57 }
 58 
 59 int c[maxn];
 60 ll mi[maxn << 2], cov[maxn << 2];
 61 void pushDown(int rt){
 62     if(cov[rt]){
 63         cov[rt << 1] += cov[rt];
 64         cov[rt << 1  1] += cov[rt];
 65         mi[rt << 1] += cov[rt];
 66         mi[rt << 1  1] += cov[rt];
 67         cov[rt] = 0;
 68     }
 69 }
 70 void pushUp(int rt){
 71     mi[rt] = min(mi[rt << 1], mi[rt << 1  1]);
 72 }
 73 void Update(int L, int R, int val, int l, int r, int rt){
 74     if(L <= l && R >= r){
 75         mi[rt] += val;
 76         cov[rt] += val;
 77         return;
 78     }
 79     pushDown(rt);
 80     int m = (l + r) >> 1;
 81     if(L <= m) Update(L, R, val, lson);
 82     if(R > m) Update(L, R, val, rson);
 83     pushUp(rt);
 84 }
 85 void farm() {
 86     int i,j,k;
 87     REP(i,n)c[i]=i;
 88     sort(c,c+n,cmp2);
 89     REP(i,n)a[c[i]].no=i+1;
 90     ///a[i].no = 1~n
 91     mz(mi);
 92     mz(cov);
 93     for(int i=0; i<n; i++){
 94         //printf("%d %d\n", a[i].no, a[i].money);
 95         Update(a[i].no, n, a[i].money, 1, n, 1);
 96         ll ans = min(mi[1], 0LL);
 97         printf("%I64d\n",ans);
 98     }
 99 }
100 
101 int main() {
102     //RE;
103     int i;
104     while(scanf("%d",&n)!=EOF) {
105         REP(i,n)scanf(" %d%d.%d%d:%d",&a[i].money , &a[i].day , &a[i].month , &a[i].hour, &a[i].mini);
106         farm();
107     }
108     return 0;
109 }
View Code

 

更多相关文章
一周排行
  • /// <summary> /// 基于.NET 3.5的Chart工具类;对应的DevExpress版本:12.1.7; /// </summary> public static class ...
  • declare @IDList as varchar(max) declare @ID as int declare @i as int set @IDList='' select @[email protected] +
  • Libgdx中有个类Actions, 从它开始顺藤摸瓜就能把哪些简单的Action快速掌握 见代码: 1 public class ActionTestScreen implements Screen,InputPr
  • 因为现在用的VS2010,发现,这个工具自己就带着ILDASM.EXE这个反编译工具 具体的查找方式为:                      C:\Program Files\Microsoft SDKS\Wi
  • C#操作xml SelectNodes,SelectSingleNode總是返回NULL 與 xPath 介紹
    一. SelectNodes,SelectSingleNode总是返回NULL    下面 ...
  • 1 linux安装盘挂载,安装日语语言包 2 linux的系统语言设置为日语 3 firefox的 edit-> setting -> contents -> language setting,添加 ...
  • 今天做实验为了好识别机器随手用 hostname source 命令更改了linux主机名然后启动数据库报如下错误: [[email protected] dbs]$ sqlplus / as sysdba SQL*Plus ...
  • [ArraySizeHelper解析] 以下代码用于获取一个数组的元素个数,例如 int table[100],以下宏返回100. template <typename T, size_t N> char ...
  • 暴力打表. 1 #include <cstdio> 2 int a[25]={0,0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0 ...
  • 我做了一个observer的设计模式实现 version1 // -- function Subject(){} Subject.prototype.add = function(obj) { if(typeof(o ...