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

 

更多相关文章
一周排行
  • 


    		    Symmetric NAT與Cone NAT
    现在我们知道,通过NAT,,内网的计算机向外连结是很容易的.NAT对于内网和外网的计算机是 ...
  • 这是一道常见的面试题,在实际项目中经常会用到. 需求:求出以产品类别为分组,各个分组里价格最高的产品信息. 实现过程如下: declare @t table( ProductID int, ProductName v
  • 和Heroes Of Might And Magic 相似,题目的询问是dp的一个副产物. 距离是不好表示成状态的,但是可以换一个角度想,如果知道了从一个点向子树走k个结点的最短距离, 那么就可以回答走x距离能访问到
  • 


    		    無法登陸SEPM11控制台解決辦法
    由于修改客户端或重装客户端的SEP导致StandardHost[localhost]: R ...
  • 文章出处:www.net1980.com Eth-Trunk接口是一种可以动态创建的接口,该类型接口可以綁定若干物理的以太网接口作为一个逻辑接口使用.加入到Eth-Trunk接口的以太网接口称为成员接口.用户只需对E
  • 入门 My first Modern UI app (manually)                          第一个ModernUI应用(手动编写)(已完成) My first Modern UI ap
  • 今天团队主要进行了用户使用的部分,因为软件操作相对来说比较复杂,因为要改很多东西,比方用户注册,还有更改软件连接服务器的IP.所以我们需要对用户进行详细地讲解.
  • #!/bin/sh # 参考文章: # 1. MFGTool Emmc mksdcard.sh MFGTool Emmc mksdcard.sh comment # http://jordonwu.github.io ...
  • 在OpenResty中使用luazlib的方法
    ============================================= ...
  • RE了几十发,实在没辦法了…只好向管理员要数据,然后发现数据规模与题目描述不符… 建立Trie并求出DFS序,同时根据DFS序确定字典序 然后每次询问相当于询问子树第k小,用主席树维护,注意压缩内存 时间复杂度$O(