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

 

更多相关文章
一周排行
  • Kafka實戰-KafkaOffsetMonitor
    1.概述 前面给大家介绍了Kafka的背景以及一些应用场景,并附带上演示了Kafka的简单
  • 必须先确定js与php两边的加密模式.秘钥,否则不能相互解开. php加密: function encrypt($data='hello,axl'){ $screct_key = '1234567899876543' ...
  •   1.解压 unzip opencv-2.4.9.zip 2.进入目录,cmake CMakeLists.txt  生成build文件 3.使用命令 make 编译 4.使用命令 make install 安装 安
  • Ref:Android Service与Activity之间通信的几种方式 Ref:基础总结篇之五:BroadcastReceiver应用详解 Ref:Android Activity和Intent机制学习笔记 Re
  •       本人邮箱:[email protected],欢迎交流讨论.       欢迎转载,转载请注明网址:http://www.cnblogs.com/JohnTsai/p/3993488.html
  • http://86asm.iteye.com/blog/976019
  • 在Ubuntu 64位OS上運行hadoop2.2.0重新編譯hadoop
    最近在学习搭建Hadoop, 我们从Apache官方网站直接下载最新版本Hadoop2.2 ...
  • 其它的代码就不贴了,直接上关键代码: $objPHPExcel = new PHPExcel(); $objPHPExcel->setActiveSheetIndex(0); $objActSheet = $o ...
  • 微软私有云解决方案包含三个核心产品,分别为Hyper-V.Windows Server和System Center.近期微软推出System Center 2012版,由此带来的新一代私有云平台将为企业带来怎样的体验
  • 本篇文章由:http://xinpure.com/codeigniter-mongodb-extension-using-aggregate-sum-method/ Codeigniter MongoDB扩展之使用A