51 条题解
-
7
刷题去 LV 10 @ 2017-07-15 17:13:21
线段树碰线过。。
Accepted # 状态 耗时 内存占用 #1 Accepted 3ms 4.34MiB #2 Accepted 3ms 4.25MiB #3 Accepted 4ms 4.25MiB #4 Accepted 4ms 4.316MiB #5 Accepted 5ms 4.25MiB #6 Accepted 5ms 4.25MiB #7 Accepted 30ms 8.625MiB #8 Accepted 39ms 6.422MiB #9 Accepted 50ms 6.297MiB #10 Accepted 66ms 5.375MiB #11 Accepted 63ms 10.977MiB #12 Accepted 69ms 11.027MiB #13 Accepted 106ms 7.293MiB #14 Accepted 79ms 7.324MiB #15 Accepted 386ms 22.543MiB #16 Accepted 537ms 22.422MiB #17 Accepted 693ms 22.418MiB #18 Accepted 846ms 22.668MiB #19 Accepted 1003ms 23.625MiB #20 Accepted 1051ms 23.875MiB 代码 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int MAX = 1000000 + 2; using namespace std; int tree[MAX * 8]; int data[MAX]; int lazy[MAX * 8]; int n, m, tot; void check(int rt) { if(tree[rt] < 0) { printf("-1\n%d", tot); exit(0); } } void up(int rt) { tree[rt] = min(tree[rt << 1] , tree[rt << 1 | 1]); check(rt); } void built(int l, int r, int rt) { if(l == r) { tree[rt] = data[l]; return; } int m = l + (r - l) / 2; built(l, m, rt << 1); built(m + 1, r, rt << 1 | 1); up(rt); } void down(int rt, int L, int R) { if(lazy[rt]) { int m = L + (R - L) / 2; lazy[rt * 2] += lazy[rt]; lazy[rt * 2 + 1] += lazy[rt]; tree[rt * 2] -= lazy[rt]; tree[rt * 2 + 1] -= lazy[rt]; lazy[rt] = 0; } } void modify(int L, int R, int l, int r, int val, int rt) { if(L >= l && R <= r) { tree[rt] -= val; check(rt); lazy[rt] += val; return; } check(rt); down(rt, L, R); int m = L + (R - L) / 2; if(m >= l) modify(L, m, l, r, val, rt * 2); if(m < r) modify(m + 1, R, l, r, val, rt * 2 + 1); up(rt); } void solve(int n, int m) { int a, b, c; for(int i = 1; i <= m; i++) { tot = i; scanf("%d %d %d", &c, &a, &b); modify(1, n, a, b, c, 1); } printf("0"); return; } void init(int n, int m) { for(int i = 1; i <= n; i++) scanf("%d", &data[i]); built(1, n, 1); } int main() { // freopen("in.txt","r", stdin); scanf("%d %d", &n, &m); init(n, m); solve(n, m); return 0; } -
3
坑点：
1.修改前缀和时要在上一个状态进行修改，不能从头到尾加
2.需要在一开始特判全都能过，否则一TLE一WA
3.并不需要开long long
还有一些细碎的二分之类，自己注意#include<iostream> #include<cstring> using namespace std; int a[1000100],qian[1000010],gai[1000010]; struct cun{ int tou,wei,shu; }q[1000010]; int main() { int n,i,left,right,mid,ci,m,last=1,haha=0,ans; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; } for(i=1;i<=m;i++) cin>>q[i].shu>>q[i].tou>>q[i].wei; left=0; right=m; for(i=1;i<=m;i++) { gai[q[i].tou]+=q[i].shu; gai[q[i].wei+1]-=q[i].shu; } for(i=1;i<=n;i++) { qian[i]=qian[i-1]+gai[i]; if(qian[i]>a[i]) break; } if(i>n) { cout<<0; return 0; } memset(qian,0,sizeof(qian)); memset(gai,0,sizeof(gai)); while(left<=right) { mid=(left+right)/2; if(mid>haha) { for(i=haha+1;i<=mid;i++) { gai[q[i].tou]-=q[i].shu; gai[q[i].wei+1]+=q[i].shu; } } else { for(i=mid+1;i<=haha;i++) { gai[q[i].tou]+=q[i].shu; gai[q[i].wei+1]-=q[i].shu; } } haha=mid; for(i=1;i<=n;i++) { qian[i]=qian[i-1]+gai[i]; if(qian[i]+a[i]<0) break; } if(i>n) { left=mid+1; } else { ans=mid; right=mid-1; } } cout<<-1<<endl; cout<<ans; return 0; } -
2
一道较为基础的线段树题目。
大体的思路是每输入一组数据，用find函数查看一下是否可行；
如果可以，就调用add函数改变线段树中的数值；
如果不行，就输出-1，还有当前的申请序号，return 0；
如果一直没有return 0，说明都可以，输出0，return 0；
对于find函数大体思路：
区间最值与给的教室数大小关系的判断，都可以就可以，任何一个不行就都不行；
对于add函数大体思路：
当find发现可以借的时候才调用；
线段树对于区间最值的维护，对于符合的根节点tree[i]-=教室数；
并用lazy数组维护；
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int tree[24000010],a[600010],lazy[24000010],n,m,s,r,ans;
void read(int &x)
{
x=0;
char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
}
void build(int x,int l,int r)
{
if (l==r)
{
tree[x]=a[l];
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
tree[x]=min(tree[x<<1],tree[x<<1|1]);
}
void pushdown(int node,int l,int r)
{
tree[node<<1]+=lazy[node];
lazy[node<<1]+=lazy[node];
tree[node<<1|1]+=lazy[node];
lazy[node<<1|1]+=lazy[node];
lazy[node]=0;
}
void add(int node,int l,int r,int x,int y,int z)
{
if (l==x&&r==y)
{
tree[node]-=z;
lazy[node]-=z;
return;
}
if (lazy[node]) pushdown(node,l,r);
int mid=(l+r)>>1;
if (y<=mid)
add(node<<1,l,mid,x,y,z);
else
if (mid<x)
add(node<<1|1,mid+1,r,x,y,z);
else
{
add(node<<1,l,mid,x,mid,z);
add(node<<1|1,mid+1,r,mid+1,y,z);
}
tree[node]=min(tree[node<<1],tree[node<<1|1]);
}
bool find(int node,int l,int r,int x,int y,int z)
{
if(r==y&&x==l)
{
if (tree[node]>=z)
return true;
else
return false;
}
if (lazy[node]) pushdown(node,l,r);
int mid=(l+r)/2;
if (y<=mid)
return find(node<<1,l,mid,x,y,z);
else
if (x>mid)
return find(node<<1|1,mid+1,r,x,y,z);
else
return find(node<<1,l,mid,x,mid,z)&find(node<<1|1,mid+1,r,mid+1,y,z);
}
int main()
{
read(n);
read(m);
for(int i=1;i<=n;i++)
read(a[i]);
build(1,1,n);
for (int i=1;i<=m;i++)
{
int x,y,z;
read(z);
read(x);
read(y);
if (find(1,1,n,x,y,z))
{
add(1,1,n,x,y,z);
}
else
{
cout<<-1<<endl;
cout<<i<<endl;
return 0;
}
}
cout<<0<<endl;
} -
1
二分答案
知识准备：使用前缀数组处理数组区间标记，单点查询。
定义sum[i]=j ，假设我们要修改多个区间 [a,b]，区间中每个元素都+c；然后我们询问每一个点，问值为多少？（N<=100w）
如果真正去标记区间[a,b]的话，时间复杂度为 O(n^2) ，显然不行。
那么我们就用一种特殊的方法来处理：
sum[a] + = c; sum[ b + 1 ] - = c;
然后我们从前到后对sum数组累加，每累加一次sum[i]就会得到点i的值。
前缀数组标记的时间复杂度为O(1),单点查询的复杂度为O(n);
借教室的题意分析：从前到后找到第一个不符合要求的订单即可！
也就是check (1,ans-1)==1;
而check (1,ans)==0的那个点ans。显然符合二分的思想，二分的是订单的编号，难点就是如何维护前缀数组sum[ ] ?
我们引入now变量，初值为0，记录当前sum数组中已经记录了从1到now的所有的订单的数据。Int mid=(l+r)>>1;
if(now<mid) 说明要把[now+1,mid]的订单加入到sum数组。
else(now>=mid) 说明要把[mid+1,now]的订单从sum数组中删除。
然后更新now=mid。
本题还有一个难点就是如何确定二分答案的左右端点！
左端点很好得出，可以为0或者1
右端点就有说道了，因为有一种情况是所有的订单都满足和第m个订单不满足情况的区别。
所有我们引入一个多余的空订单，即右端点r=m+1.
庆幸的是输出“0”的测试点并不多——防骗分。#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int f,n; int room[1000001],d[1000001],c[1000001]; int s[1000001],t[1000001],a[1000001]; bool check(int k) { if(k>f) { for(int i=f+1;i<=k;i++) { a[s[i]]-=d[i]; a[t[i]+1]+=d[i]; } } else { for(int i=k+1;i<=f;i++) { a[s[i]]+=d[i]; a[t[i]+1]-=d[i]; } } f=k; for(int i=1;i<=n;i++) { c[i]=c[i-1]+a[i]; if(c[i]+room[i]<0) return false; } return true; } int main() { int m,ans; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&room[i]); } for(int i=1;i<=m;i++) { scanf("%d%d%d",&d[i],&s[i],&t[i]); } int l=1,r=m+1; while(l<r) { int mid=(l+r)>>1; if(check(mid)) l=mid+1; else r=mid; } if(check(m)) { printf("0"); return 0; } printf("-1\n%d",l); return 0; } -
1
2351599120 LV 9 @ 2017-10-27 17:00:06
二分答案
跑的飞起#include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <cctype> #include <vector> #include <queue> using namespace std; int f,n; int room[1000001],mon[1000001],c[1000001]; int s[1000001],t[1000001],a[1000001]; bool check(int k) { if(k>f) { for(int i=f+1;i<=k;i++) { a[s[i]]-=mon[i]; a[t[i]+1]+=mon[i]; } } else { for(int i=k+1;i<=f;i++) { a[s[i]]+=mon[i]; a[t[i]+1]-=mon[i]; } } f=k; for(int i=1;i<=n;i++) { c[i]=c[i-1]+a[i]; if(c[i]+room[i]<0) { return false; } } return true; } int main() { int m,l=0,r,mid,ans; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&room[i]); } for(int i=1;i<=m;i++) { scanf("%d%d%d",&mon[i],&s[i],&t[i]); } r=m; if(check(m)==true) { printf("0"); return 0; } while(l<=r) { mid=(l+r)/2; if(check(mid)==true) { l=mid+1; } else { ans=mid; r=mid-1; } } printf("-1\n%d",ans); return 0; } -
1
二分答案。。。常数优化写不下去了就这样吧。。。交上去之后还挺快
依旧是循环展开+读入优化+寄存器变量，没啥新鲜的#include <cstdio> #include <cctype> const int MAXN = 1000010; int n, m, ans, a[MAXN], s[MAXN], t[MAXN], k[MAXN]; //读入优化 inline int ReadInt() { char _c; int sum(0); while (!isdigit(_c = getchar())); do sum = sum * 10 + _c - '0'; while (isdigit(_c = getchar())); return sum; } //其实judge也是可以搞些小优化的但是我不想写了。。。 inline bool judge(int x) { //memset(num, 0, sizeof(num)); int num[MAXN] = {0}; //我猜测这样可能比memset快一些 for (register int i = 1; i <= x; ++i) num[s[i]] += k[i], num[t[i] + 1] -= k[i]; register int sa(0); for (register int i = 1; i <= n; ++i) { sa += num[i]; if (sa > a[i]) return false; } return true; } int main() { //前方高能，密集恐惧症患者慎入【滑稽 //好多的ReadInt() n = ReadInt(), m = ReadInt(); for (register int i = 1; i < n; i += 2) a[i] = ReadInt(), a[i + 1] = ReadInt(); (n & 1) && (a[n] = ReadInt()); //这里就是if else好孩子不要学 for (register int i = 1; i < m; i += 2) k[i] = ReadInt(), s[i] = ReadInt(), t[i] = ReadInt(), k[i + 1] = ReadInt(), s[i + 1] = ReadInt(), t[i + 1] = ReadInt(); (m & 1) && (k[m] = ReadInt(), s[m] = ReadInt(), t[m] = ReadInt()); register int l = 1, r = m, mid = -1; while (l <= r) { mid = (l + r) >> 1; (judge(mid)) ? (l = mid + 1, ans = mid) : (r = mid - 1); } //其实这里还可以写的更优美 (ans < m) ? printf("-1\n%d\n", ans + 1) : printf("0\n"); return 0; }qwq就是这样
#1 Accepted 8ms 10.0MiB
#2 Accepted 7ms 10.0MiB
#3 Accepted 10ms 10.07MiB
#4 Accepted 10ms 10.094MiB
#5 Accepted 8ms 10.07MiB
#6 Accepted 10ms 10.0MiB
#7 Accepted 39ms 10.488MiB
#8 Accepted 45ms 10.469MiB
#9 Accepted 44ms 12.418MiB
#10 Accepted 48ms 16.051MiB
#11 Accepted 46ms 12.496MiB
#12 Accepted 43ms 14.527MiB
#13 Accepted 44ms 12.508MiB
#14 Accepted 45ms 14.598MiB
#15 Accepted 289ms 19.301MiB
#16 Accepted 317ms 19.305MiB
#17 Accepted 349ms 19.539MiB
#18 Accepted 367ms 19.406MiB
#19 Accepted 395ms 19.301MiB
#20 Accepted 393ms 19.305MiB比线段树要快
-
vonhyou @ 2017-08-11 21:23:08
其实我一开始也是想的线段树，但是我本地测的貌似有卡线段树的数据，需要优化
-
call_me_std @ 2017-10-25 11:32:21
全部加register啊！
为啥用咸鱼读优不写iobuff或者mmap? -
全部加register啊！
为啥用咸鱼读优不写iobuff或者mmap? -
@call_me_std: qwq好久之前写题全用register挂掉了。。。至于后两个我第一次听说qwq待我去学学
-
@call_me_std: %%%谢谢dalao
-
-
1
LN_handsome LV 9 @ 2015-11-02 17:42:42
var a,ca,d,s,t:array[0..1000005] of longint;
i,j,k,l,n,m,r,o,now:longint;
tmt,ans:int64;
p:boolean;
begin
read(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to m do read(d[i],s[i],t[i]);
d[m+1]:=a[1]+1; s[m+1]:=1; t[m+1]:=1;
l:=1; r:=m+1; now:=0;
while l<=r do
begin
ans:=l+((r-l) shr 1);
if ans>now then
for i:=now+1 to ans do
begin
inc(ca[s[i]],d[i]);
dec(ca[t[i]+1],d[i]);
end
else
for i:=ans+1 to now do
begin
dec(ca[s[i]],d[i]);
inc(ca[t[i]+1],d[i]);
end;
now:=ans;
tmt:=0;
p:=true;
for i:=1 to n do
begin
tmt:=tmt+ca[i];
if tmt>a[i] then begin p:=false; break; end;
end;
if p then l:=ans+1
else r:=ans-1;
end;
if l=m+1 then writeln(0)
else
begin
writeln(-1);
writeln(l);
end;
end.
数组把int64改成longint，最慢的从900+ms变成了600+ms，洛谷上更是从超时两个点到最慢的600+ms，告诉我为什么。
思路：恩二分的话不用讲，然后就是判断满不满足的部分。
用到了一个记录的数组，这个数组的性质是：ca[i]表示a[i]这个数比a[i-1]大ca[i]，然后我想你已经知道了。
这个数组其实就是记录一个差值，然后使区间加减的复杂度变成了O（1），但是查询就是O（n）（查询一个和查询N个复杂度一样）。 -
0
Mark__Zuckerburg LV 8 @ 2018-02-11 11:09:07
差分+二分答案
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; #define Maxn 1000001 long long n,m,s[Maxn],t[Maxn],le,ri,mid,ans,sum[Maxn]; long long r[Maxn],d[Maxn],minn=Maxn,e; bool check(long long x) { memset(sum,0,sizeof(sum)); for(int i=1;i<=x;i++) { sum[s[i]]+=d[i]; sum[t[i]+1]-=d[i]; } long long ss=0; for(int i=1;i<=n;i++) { ss+=sum[i]; if(ss>r[i]) { minn=min(minn,x); return false; } } return true; } int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>r[i]; for(int i=1;i<=m;i++) cin>>d[i]>>s[i]>>t[i]; le=1; ri=m; while(le<ri) { mid=(le+ri)/2; if(check(mid)) le=mid+1; else ri=mid; } if(minn==Maxn) cout<<0; else cout<<-1<<endl,cout<<minn<<endl; return 0; }就完事了
-
0
wanghaozhou LV 8 @ 2017-10-24 23:01:24
Lazy线段树，1234ms居然没TLE
状态 耗时 内存占用
#1 Accepted 4ms 380.0 KiB
#2 Accepted 4ms 348.0 KiB
#3 Accepted 3ms 384.0 KiB
#4 Accepted 4ms 372.0 KiB
#5 Accepted 4ms 360.0 KiB
#6 Accepted 4ms 348.0 KiB
#7 Accepted 42ms 3.219 MiB
#8 Accepted 57ms 3.734 MiB
#9 Accepted 76ms 3.836 MiB
#10 Accepted 96ms 2.375 MiB
#11 Accepted 104ms 2.859 MiB
#12 Accepted 116ms 2.492 MiB
#13 Accepted 150ms 4.25 MiB
#14 Accepted 116ms 3.082 MiB
#15 Accepted 440ms 18.121 MiB
#16 Accepted 619ms 17.84 MiB
#17 Accepted 859ms 17.824 MiB
#18 Accepted 943ms 16.742 MiB
#19 Accepted 1185ms 18.117 MiB
#20 Accepted 1234ms 18.461 MiB#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<iostream> using namespace std; template<class T> inline void read(T &_a){ bool f=0;int _ch=getchar();_a=0; while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();} while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();} if(f)_a=-_a; } const int maxn=1000001; struct fff { int minn,lazy; }node[(maxn<<2)+(maxn<<1)]; int n,m; inline void pushup(int u) { node[u].minn=min(node[u<<1].minn,node[u<<1|1].minn); } inline void pushdown(int u) { if(node[u].lazy) { node[u<<1].lazy+=node[u].lazy; node[u<<1|1].lazy+=node[u].lazy; node[u<<1].minn-=node[u].lazy; node[u<<1|1].minn-=node[u].lazy; node[u].lazy=0; } } void build(int u,int l,int r) { if(l==r) { read(node[u].minn); return ; } int mid=(l+r)>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } int query(int u,int l,int r,int L,int R) { if(L<=l&&r<=R) return node[u].minn; pushdown(u); int mid=(l+r)>>1; if(R<=mid) return query(u<<1,l,mid,L,R); if(L>mid) return query(u<<1|1,mid+1,r,L,R); return min(query(u<<1,l,mid,L,R),query(u<<1|1,mid+1,r,L,R)); } void update(int u,int l,int r,int L,int R,int val) { if(L<=l&&r<=R) { node[u].lazy+=val; node[u].minn-=val; return ; } pushdown(u); int mid=(l+r)>>1; if(L<=mid) update(u<<1,l,mid,L,R,val); if(R>mid) update(u<<1|1,mid+1,r,L,R,val); pushup(u); return ; } int main() { read(n); read(m); build(1,1,n); for (register int cas=1,d,s,j;cas<=m;++cas) { read(d); read(s); read(j); int num=query(1,1,n,s,j); if(num<d) {printf("-1\n%d",cas); return 0;} update(1,1,n,s,j,d); } printf("0"); return 0; } -
0
xianggulinger LV 8 @ 2017-10-17 20:10:38
二分：
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks) #define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks) int n, m; int ma[5000000]; int nu[5000000], be[5000000], ed[5000000]; int oka[5000000]; bool ok(int x){ For(i, 1, n){ oka[i] = 0; } For(i, 1, x){ oka[be[i]] += nu[i]; oka[ed[i] + 1] -= nu[i]; } int t = 0; For(i, 1, n){ t += oka[i]; if (t > ma[i]){ return false; } } return true; } int bi(int l, int r){ if (l == r){ return l; } int t = (l + r) / 2; if (ok(t)){ return bi(t + 1, r); } else{ return bi(l, t); } } int main(){ cin >> n >> m; For(i, 1, n){ cin >> ma[i]; } For(i, 1, m){ cin >> nu[i] >> be[i] >> ed[i]; } if (ok(m)){ cout << 0 << endl; return 0; } int ans = bi(1, m); cout << -1 << endl << ans << endl; return 0; } /* * 5 2 100 10001 100 1000 1000 1 2 3 1 1 2 */线段树：
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks) #define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks) int l[10000000], r[10000000], ma[10000000], mi[10000000], sp[10000000]; int n, m; void in(int le, int ri, int k){ l[k] = le; r[k] = ri; if (le == ri){ mi[k] = ma[le]; return; } int mid = (le + ri) / 2; in(le, mid, 2 * k); in(mid + 1, ri, 2 * k + 1); mi[k] = min(mi[2 * k], mi[2 * k + 1]); } int smi(int gl, int gr, int k){ if (gl == l[k] && gr == r[k]){ return (mi[k] + sp[k]); } int pm = (l[k] + r[k]) / 2; if (gr <= pm){ return (smi(gl, gr, 2 * k) + sp[k]); } if (gl >= pm + 1){ return (smi(gl, gr, 2 * k + 1) + sp[k]); } return (min(smi(gl, pm, 2 * k), smi(pm + 1, gr, 2 * k + 1)) + sp[k]); } void oc(int gl, int gr, int gn, int k){ if (gl == l[k] && gr == r[k]){ sp[k] -= gn; return; } int pm = (l[k] + r[k]) / 2; if (gr <= pm){ oc(gl, gr, gn, 2 * k); mi[k] = min(mi[2 * k] + sp[2 * k], mi[2 * k + 1] + sp[2 * k + 1]); return; } if (gl >= pm + 1){ oc(gl, gr, gn, 2 * k + 1); // mi[k] = min(smi(gl, pm, 2 * k), smi(pm + 1, gr, 2 * k + 1)); mi[k] = min(mi[2 * k] + sp[2 * k], mi[2 * k + 1] + sp[2 * k + 1]); return; } oc(gl, pm, gn, 2 * k); oc(pm + 1, gr, gn, 2 * k + 1); // mi[k] = min(smi(gl, pm, 2 * k), smi(pm + 1, gr, 2 * k + 1)); mi[k] = min(mi[2 * k] + sp[2 * k], mi[2 * k + 1] + sp[2 * k + 1]); } int main(){ cin >> n >> m; For(i, 1, n){ scanf("%d", &ma[i]); } in(1, n, 1); For(tosn, 1, m){ int num, be, en; cin >> num >> be >> en; // cout << smi(be, en, 1) << ' '; // cout << smi(be, en, 1) << endl; if (smi(be, en, 1) < num){ cout << -1 << endl << tosn << endl; return 0; } oc(be, en, num, 1); // For(i, 1, n){ // cout << smi(i, i, 1) << ' '; // } // // cout << endl; } cout << 0 << endl; return 0; } -
0
Sky1231 (sky1231) LV 10 @ 2017-08-13 16:35:37
2分
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <algorithm> #include <vector> #include <deque> #include <limits> #include <string> #include <sstream> using namespace std; const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f; int n,m; int a[1048576+1]; int s[1048576+1]; int t[1048576+1]; int num[1048576+1]; int sum[1048576+1]; int check_1(int x) { memset(sum,0,sizeof(sum)); for (int i=1;i<=x;i++) sum[s[i]]+=num[i],sum[t[i]+1]-=num[i]; int ans=0; for (int i=1;i<=n;i++) { ans+=sum[i]; if (ans>a[i]) return 0; } return 1; } int main() { while (~scanf("%d%d",&n,&m)) { for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=m;i++) scanf("%d%d%d",&num[i],&s[i],&t[i]); int left,right; for (left=1,right=m;right-left>1;) { int mid=(left+right)/2; if (check_1(mid)) left=mid; else right=mid; } int ans=oo_max; if (check_1(left)==0) ans=left; else if (check_1(right)==0) ans=right; if (ans<oo_max) { printf("%d\n",-1); printf("%d\n",ans); } else printf("%d\n",0); } }Segment Tree
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <algorithm> #include <vector> #include <deque> #include <limits> #include <string> #include <sstream> using namespace std; const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f; struct segment_tree_1 { int l,r,mid,x,lazy; }st[2*1048576+2]; int n,m; int a[1048576+1]; void build_segment_tree_1(int now,int l,int r) { st[now].l=l,st[now].r=r,st[now].mid=(l+r)/2,st[now].lazy=0; if (l<r) { if (l<=st[now].mid) build_segment_tree_1(now*2,l,st[now].mid); if (st[now].mid+1<=r) build_segment_tree_1(now*2+1,st[now].mid+1,r); } if (l==r) st[now].x=a[l]; else st[now].x=min(st[now*2].x,st[now*2+1].x); } void push_down_1(int now) { if (st[now].lazy) { st[now*2].lazy+=st[now].lazy,st[now*2+1].lazy+=st[now].lazy; st[now*2].x-=st[now].lazy,st[now*2+1].x-=st[now].lazy; st[now].lazy=0; } } void update_1(int now,int l,int r,int x) { if (st[now].l==l&&st[now].r==r) { st[now].x-=x; st[now].lazy+=x; return; } else { push_down_1(now); if (r<=st[now].mid) update_1(now*2,l,r,x); else if (st[now].mid+1<=l) update_1(now*2+1,l,r,x); else update_1(now*2,l,st[now].mid,x),update_1(now*2+1,st[now].mid+1,r,x); st[now].x=min(st[now*2].x,st[now*2+1].x); } } int sum_1(int now,int l,int r) { if (st[now].l==l&&st[now].r==r) return st[now].x; else { push_down_1(now); if (r<=st[now].mid) return sum_1(now*2,l,r); else if (st[now].mid+1<=l) return sum_1(now*2+1,l,r); else return min(sum_1(now*2,l,st[now].mid),sum_1(now*2+1,st[now].mid+1,r)); } } int main() { while (~scanf("%d%d",&n,&m)) { int flag=0; for (int i=1;i<=n;i++) scanf("%d",&a[i]); build_segment_tree_1(1,1,n); for (int i=1;i<=m;i++) { int l,r,x; scanf("%d%d%d",&x,&l,&r); if (flag==0) { if (sum_1(1,l,r)>=x) update_1(1,l,r,x); else { printf("%d\n",(flag=-1)); printf("%d\n",i); } } } if (flag==0) printf("%d\n",flag); } }-
很H2O的题
-
-
0
2012NOIP DAY2T1
方法1：线段树
使用线段树来维护一个区间的最小值，每次对于输入的L,R区间进行区间修改，如果最小值<0，则无法成功借教室（加了一大堆玄学优化，终于勉强没T）#include <cstdio> #include <stdlib.h> using namespace std; const int maxn=1e6+100; struct tree{ int minn; int l,r; int adi; }st[maxn*4]; int a[maxn]; int w; inline int min(int a,int b) { return a < b ? a : b; } void build(int o,int l,int r) { st[o].l=l,st[o].r=r; if(l==r) { st[o].minn=a[l]; return; } int mid=(r+l)>>1; build((o<<1),l,mid); build((o<<1)|1,mid+1,r); st[o].minn=min(st[(o<<1)].minn,st[(o<<1)|1].minn); } inline void push_down(int o) { int add=st[o].adi; st[o].adi=0; st[(o<<1)].adi+=add; st[(o<<1)|1].adi+=add; st[(o<<1)].minn+=add; st[(o<<1)|1].minn+=add; } inline void query(int o,int ql,int qr,int ad) { int l=st[o].l,r=st[o].r; if(l==ql&&r==qr) { st[o].adi+=ad; st[o].minn+=ad; if(st[o].minn<0) { printf("-1\n%d\n",w); exit(0); } return; } if(st[o].adi) push_down(o); int mid=(l+r)>>1; if(qr<=mid) query((o<<1),ql,qr,ad); else if(ql>mid) query((o<<1)|1,ql,qr,ad); else query((o<<1),ql,mid,ad),query((o<<1)|1,mid+1,qr,ad); st[o].minn=min(st[(o<<1)].minn,st[(o<<1)|1].minn); } inline int read() { int data=0,w=1; char ch=0; while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar(); return data*w; } int main() { int n,m; n=read(); m=read(); for (int i = 1; i <= n; i++) { char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') { a[i] *= 10; a[i] += c - '0'; c = getchar(); } } build(1,1,n); for(int i=1;i<=m;i++) { int x,y,t; t=read(); x=read(); y=read(); w=i; query(1,x,y,-t); } printf("0"); return 0; }方法2：二分+差分
二分能够成功的方案数，用差分进行区修改，暴力判断有没有超出限制的，时间复杂度O（nlogn）
其实跟线段树的复杂度相同，只是常数比较小，在数据爆炸的题里会快不少！#include <cstdio> #include <stdlib.h> #include <iostream> #include <cstring> using namespace std; const int maxn=1001000; struct tree{ int l,r,t; }a[maxn]; int d[maxn]; int b[maxn]; inline int read() { int data=0,w=1; char ch=0; while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar(); return data*w; } int n,m; inline bool check(int mid) { memset(b,0,sizeof(b)); for(int i=1;i<=mid;i++) b[a[i].l]+=a[i].t,b[a[i].r+1]-=a[i].t; int s=0; for(int i=1;i<=n;i++) { s+=b[i]; if(s>d[i]) return 0; } return 1; } int main() { n=read(); m=read(); for(int i=1;i<=n;i++) d[i]=read(); for(int i=1;i<=m;i++) a[i].t=read(),a[i].l=read(),a[i].r=read(); int l=1; int r=m; int ans=0; while(l<=r) { int mid=(l+r)/2; if(!check(mid)) ans=mid,r=mid-1; else l=mid+1; } if(!ans) printf("0"); else printf("-1\n%d",ans); return 0; } -
0
一击！！！
#include<iostream> #include<cstdio> #define INF (0x3f3f3f3f) using namespace std; struct DA {int d,s,t;} da[1000010]; struct SGT {int l,r,mi,lz;} sgt[1000010<<2]; int n,m; int spt[1000010]; int rint () {int num=0,f=1;char cc=getchar();while(cc<'0'||cc>'9') {if (cc=='-') f=-1;cc=getchar();}while(cc>='0'&&cc<='9') {num=num*10+cc-'0';cc=getchar();}return num*f;} void sgtps (int id) {sgt[id].mi=min(sgt[id<<1].mi,sgt[id<<1|1].mi);return;} void sgtdn (int id) { sgt[id<<1].lz+=sgt[id].lz,sgt[id<<1].mi+=sgt[id].lz; sgt[id<<1|1].lz+=sgt[id].lz,sgt[id<<1|1].mi+=sgt[id].lz; sgt[id].lz=0; } void sgtbd (int l,int r,int id) { sgt[id].l=l,sgt[id].r=r,sgt[id].lz=0; if (l==r) {sgt[id].mi=spt[l];return;} sgtbd(l,(l+r)>>1,id<<1),sgtbd(((l+r)>>1)+1,r,id<<1|1); sgtps(id); } void sgtad (int l,int r,int val,int id) { if (sgt[id].r<l||sgt[id].l>r) return; if (sgt[id].l==l&&sgt[id].r==r) {sgt[id].lz+=val,sgt[id].mi+=val;return;} sgtdn(id); if (r<((sgt[id].l+sgt[id].r)>>1)) sgtad(l,r,val,id<<1); else if (l>((sgt[id].l+sgt[id].r)>>1)) sgtad(l,r,val,id<<1|1); else sgtad(l,(sgt[id].l+sgt[id].r)>>1,val,id<<1),sgtad(((sgt[id].l+sgt[id].r)>>1)+1,r,val,id<<1|1); sgtps(id); } int sgtmi (int l,int r,int id) { if (sgt[id].r<l||sgt[id].l>r) return INF; if (sgt[id].l==l&&sgt[id].r==r) return sgt[id].mi; sgtdn(id); if (r<((sgt[id].l+sgt[id].r)>>1)) return sgtmi(l,r,id<<1); else if (l>((sgt[id].l+sgt[id].r)>>1)) return sgtmi(l,r,id<<1|1); else return min(sgtmi(l,(sgt[id].l+sgt[id].r)>>1,id<<1),sgtmi(((sgt[id].l+sgt[id].r)>>1)+1,r,id<<1|1)); sgtps(id); } int main () { ios::sync_with_stdio(false); n=rint(),m=rint(); for(int i=1;i<=n;i++) spt[i]=rint(); sgtbd(1,n,1); int flag=0; int cant; for(int i=1;i<=m;i++) { da[i].d=rint(),da[i].s=rint(),da[i].t=rint(); sgtad(da[i].s,da[i].t,-da[i].d,1); if (sgtmi(da[i].s,da[i].t,1)<0) {flag=i;break;} } if (!flag) cout<<"0"<<endl; else cout<<"-1"<<endl<<flag<<endl; return 0; } -
0
williamking5 LV 8 @ 2016-05-03 19:47:21
两件事情：
1.被卡时限的首先优化读入。
2.结构体、类封装、位运算加速在这道题里面对于程序运行时间影响很小。编译成功
测试数据 #0: Accepted, time = 46 ms, mem = 47528 KiB, score = 5
测试数据 #1: Accepted, time = 46 ms, mem = 47524 KiB, score = 5
测试数据 #2: Accepted, time = 31 ms, mem = 47524 KiB, score = 5
测试数据 #3: Accepted, time = 31 ms, mem = 47528 KiB, score = 5
测试数据 #4: Accepted, time = 31 ms, mem = 47524 KiB, score = 5
测试数据 #5: Accepted, time = 46 ms, mem = 47524 KiB, score = 5
测试数据 #6: Accepted, time = 93 ms, mem = 47528 KiB, score = 5
测试数据 #7: Accepted, time = 46 ms, mem = 47528 KiB, score = 5
测试数据 #8: Accepted, time = 62 ms, mem = 47528 KiB, score = 5
测试数据 #9: Accepted, time = 93 ms, mem = 47528 KiB, score = 5
测试数据 #10: Accepted, time = 93 ms, mem = 47524 KiB, score = 5
测试数据 #11: Accepted, time = 125 ms, mem = 47524 KiB, score = 5
测试数据 #12: Accepted, time = 125 ms, mem = 47524 KiB, score = 5
测试数据 #13: Accepted, time = 78 ms, mem = 47524 KiB, score = 5
测试数据 #14: Accepted, time = 437 ms, mem = 47528 KiB, score = 5
测试数据 #15: Accepted, time = 609 ms, mem = 47524 KiB, score = 5
测试数据 #16: Accepted, time = 734 ms, mem = 47524 KiB, score = 5
测试数据 #17: Accepted, time = 875 ms, mem = 47528 KiB, score = 5
测试数据 #18: Accepted, time = 1000 ms, mem = 47524 KiB, score = 5
测试数据 #19: Accepted, time = 1171 ms, mem = 47528 KiB, score = 5#include<bits/stdc++.h>
using namespace std;
struct INTERVAL_DATA{
int left,right,Max,lazy;
INTERVAL_DATA(){
left=right=0;
lazy=0;
Max=0;
}
};
INTERVAL_DATA tree[3000000];
inline int read( )
{
int x=0;
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
x=0;
while (ch<='9' && ch>='0')
{
x*=10,x+=ch-'0';
ch=getchar();
}
return x;
}
struct INTERVAL_TREE{
int nn;
INTERVAL_TREE(int height){
nn=height;int h=0;
tree[0].left=0;tree[0].right=(1<<nn)-1;
for (int i=0;i<((1<<nn)-1);i++){
if (i>(2<<h)-2) h++;
tree[(i<<1)+1].left=tree[i].left;
tree[(i<<1)+2].left=(1<<(nn-h-1))|tree[i].left;
tree[(i<<1)+1].right=tree[(i<<1)+1].left+(1<<(nn-h-1))-1;
tree[(i<<1)+2].right=tree[(i<<1)+2].left+(1<<(nn-h-1))-1;
}
for (int i=0;i<(2<<nn)-1;i++){
tree[i].left++;
tree[i].right++;
}
}
void add(int root,int l,int r,int x){
if (l==tree[root].left&&r==tree[root].right) tree[root].lazy+=x;
else {
int mid=(tree[root].left+tree[root].right)>>1;
tree[(root<<1)+1].lazy+=tree[root].lazy;
tree[(root<<1)+2].lazy+=tree[root].lazy;
tree[root].lazy=0;if (l>mid) add((root<<1)+2,l,r,x);
else if (r<=mid) add((root<<1)+1,l,r,x);
else {
add((root<<1)+1,l,mid,x);
add((root<<1)+2,mid+1,r,x);
}tree[root].Max=max(tree[(root<<1)+1].lazy+tree[(root<<1)+1].Max,tree[(root<<1)+2].lazy+tree[(root<<1)+2].Max);
}
}
} a(20);
int main(){
int n,m,x,y,z;
n = read();
m = read();
for (int i=0;i<n;i++){
x = read();
a.add(0,i+1,i+1,-x);
}for (int i=0;i<m;i++){
x=read();
y=read();
z=read();
a.add(0,y,z,x);
if (tree[0].Max>0) {
cout<<"-1"<<endl<<i+1<<endl;
return 0;
}
}cout<<0<<endl;
return 0;
} -
0
论**普通线段树**如何通过
编译成功 测试数据 #0: Accepted, time = 15 ms, mem = 48736 KiB, score = 5 测试数据 #1: Accepted, time = 15 ms, mem = 48740 KiB, score = 5 测试数据 #2: Accepted, time = 31 ms, mem = 48740 KiB, score = 5 测试数据 #3: Accepted, time = 15 ms, mem = 48732 KiB, score = 5 测试数据 #4: Accepted, time = 31 ms, mem = 48736 KiB, score = 5 测试数据 #5: Accepted, time = 15 ms, mem = 48736 KiB, score = 5 测试数据 #6: Accepted, time = 140 ms, mem = 48736 KiB, score = 5 测试数据 #7: Accepted, time = 140 ms, mem = 48740 KiB, score = 5 测试数据 #8: Accepted, time = 125 ms, mem = 48732 KiB, score = 5 测试数据 #9: Accepted, time = 140 ms, mem = 48732 KiB, score = 5 测试数据 #10: Accepted, time = 93 ms, mem = 48736 KiB, score = 5 测试数据 #11: Accepted, time = 101 ms, mem = 48732 KiB, score = 5 测试数据 #12: Accepted, time = 93 ms, mem = 48740 KiB, score = 5 测试数据 #13: Accepted, time = 101 ms, mem = 48732 KiB, score = 5 测试数据 #14: Accepted, time = 1671 ms, mem = 48740 KiB, score = 5 测试数据 #15: Accepted, time = 1296 ms, mem = 48736 KiB, score = 5 测试数据 #16: Accepted, time = 1250 ms, mem = 48736 KiB, score = 5 测试数据 #17: Accepted, time = 1125 ms, mem = 48732 KiB, score = 5 测试数据 #18: Accepted, time = 875 ms, mem = 48732 KiB, score = 5 测试数据 #19: Accepted, time = 843 ms, mem = 48736 KiB, score = 5 Accepted, time = 8115 ms, mem = 48740 KiB, score = 100关键在于各种**奇技淫巧的优化**，我列出一些：
1. 正确的模拟方法 +30%
2. 堆式存储 +15%
3. 将所有除以2的运算变为位运算 +3%
4. 手动优化尾递归，vijos没有开优化 +5%
5. 循环使用迭代器写法 +5%
6. 读入优化 +3%
7. 大胆的使用int +2%
8. 使用结构体的默认构造函数 +1%
9. 线段树的插入和查询操作中对每条语句的必要性进行严格检查。删去没必要的语句 +2%优化真是一件有趣的事......
实在过不了的可以到codevs上试试，codevs的机子好多了......代码：
```c++
// 借教室#include <cstdlib>
#include <string>
#include <cstdio>
#include <algorithm>using namespace std;
#define NMAX 1000000
#define MMAX 1000000
#define MEMORY_SIZE 2097151#define LEFT(x) (x << 1)
#define RIGHT(x) ((x << 1) | 1)
#define PARENT(x) (x >> 1)// #define FMT "%lld"
// typedef long long ntype;
#define FMT "%d"
typedef int ntype;struct Reservation {
Reservation() : start(0), end(0), need(0) {}
Reservation(ntype s, ntype t, ntype d) : start(s), end(t), need(d) {}ntype start;
ntype end;
ntype need;
}; // struct Reservationstruct Node {
Node() : pos(1), l(0), r(0), sum(0) {}
Node(ntype _l, ntype _r) : pos(1), l(_l), r(_r), sum(0) {}ntype pos;
ntype l;
ntype r;
ntype sum;
};static ntype n, m;
static ntype r[NMAX + 10];
static Reservation q[MMAX + 10];
static Node heap[MEMORY_SIZE];
static bool flag;
static ntype id;Node *build_tree(ntype lb, ntype rb, ntype p = 1);
void insert(ntype s, ntype t, ntype value, ntype p = 1);
ntype query(ntype d, ntype p = 1);inline ntype read() {
ntype x = 0;
char c = getchar();
while (c < '0' or c > '9') c = getchar();
while ('0' <= c and c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}void initialize();
void quit();int main() {
initialize();for (Reservation *beg = &q[1]; beg != &q[n + 1]; beg++) {
insert(beg->start, beg->end, -beg->need, 1);
} // forReservation *j = &q[m + 1];
for (ntype i = 1; i <= n; i++) {
while (query(i, 1) < 0) {
j--;
insert(j->start, j->end, j->need, 1);
} // while
} // forif (j != &q[m + 1]) {
flag = true;
id = j - &q[1] + 1;
}quit();
return 0;
} // function mainvoid initialize() {
n = read();
m = read();for (int *beg = &r[1]; beg != &r[n + 1]; beg++) *beg = read();
for (Reservation *beg = &q[1]; beg != &q[m + 1]; beg++)
beg->need = read(), beg->start = read(), beg->end = read();flag = false;
id = 0;build_tree(1, n);
}void quit() {
if (!flag)
puts("0");
else {
puts("-1");
printf(FMT, id);
}
}Node *build_tree(ntype lb, ntype rb, ntype p) {
Node *x = &heap[p];
x->l = lb;
x->r = rb;if (lb != rb) {
ntype mid = (lb + rb) >> 1;
build_tree(lb, mid, LEFT(p));
build_tree(mid + 1, rb, RIGHT(p));
} else
x->sum = r[lb];return x;
}void insert(ntype s, ntype t, ntype value, ntype p) {
recursive:
Node *x = &heap[p];if (s <= x->l and x->r <= t)
x->sum += value;
else {
ntype mid = (x->l + x->r) >> 1;if (t <= mid) {
// insert(s, t, value, LEFT(p));
p = LEFT(p);
goto recursive;
} else if (s > mid) {
// insert(s, t, value, RIGHT(p));
p = RIGHT(p);
goto recursive;
} else {
insert(s, t, value, LEFT(p));
insert(s, t, value, RIGHT(p));
}
}
}ntype query(ntype d, ntype p) {
ntype result = 0;recursive:
Node *x = &heap[p];if (d == x->l and d == x->r) return result + x->sum;
result += x->sum;
ntype mid = (x->l + x->r) >> 1;if (d <= mid)
p = LEFT(p);
else
p = RIGHT(p);goto recursive;
} -
0
你们也交交看，一样的程序有时AC有时TLE
评测结果
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 317268 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 317268 KiB, score = 5
测试数据 #2: Accepted, time = 15 ms, mem = 317272 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 317268 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #6: Accepted, time = 31 ms, mem = 317268 KiB, score = 5
测试数据 #7: Accepted, time = 31 ms, mem = 317268 KiB, score = 5
测试数据 #8: Accepted, time = 46 ms, mem = 317272 KiB, score = 5
测试数据 #9: Accepted, time = 78 ms, mem = 317272 KiB, score = 5
测试数据 #10: Accepted, time = 78 ms, mem = 317268 KiB, score = 5
测试数据 #11: Accepted, time = 93 ms, mem = 317272 KiB, score = 5
测试数据 #12: Accepted, time = 140 ms, mem = 317272 KiB, score = 5
测试数据 #13: Accepted, time = 78 ms, mem = 317268 KiB, score = 5
测试数据 #14: Accepted, time = 437 ms, mem = 317272 KiB, score = 5
测试数据 #15: Accepted, time = 703 ms, mem = 317272 KiB, score = 5
测试数据 #16: Accepted, time = 937 ms, mem = 317272 KiB, score = 5
测试数据 #17: Accepted, time = 1218 ms, mem = 317272 KiB, score = 5
测试数据 #18: Accepted, time = 1500 ms, mem = 317272 KiB, score = 5
测试数据 #19: Accepted, time = 1625 ms, mem = 317272 KiB, score = 5
Accepted, time = 7010 ms, mem = 317272 KiB, score = 100
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[1000003],p,tot;
int d,s,t;
struct arr{
int w,c;
}tr[1000003*40];int read(){
int f=1,x=0;
char s=getchar();
while(s<'0'||s>'9') s=getchar();
while(s>='0' && s<='9'){
x=x*10+(s-48);
s=getchar();
}
return f*x;
}void push(int num){
tr[2*num].c+=tr[num].c;
tr[2*num+1].c+=tr[num].c;
tr[num].w-=tr[num].c;
tr[num].c=0;
}void build(int num,int l,int r){
if (l==r){
tr[num].w=a[l];
return;
}
build(2*num,l,(l+r)/2);
build(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}int find(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return 2147483647;
if (s<=l && r<=t) return tr[num].w;
return min(find(2*num,l,(l+r)/2),find(2*num+1,(l+r)/2+1,r));
}void insert(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return;
if (s<=l && r<=t){
tr[num].w-=d;
tr[2*num].c+=d;
tr[2*num+1].c+=d;
return;
}
insert(2*num,l,(l+r)/2);
insert(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}int main(){
n=read();m=read();
for (int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
for (int i=1;i<=m;i++){
d=read();s=read();t=read();
if (tot) continue;
int dd=find(1,1,n);
if (dd<d) p=i,tot++;
else insert(1,1,n);
}
if (tot) printf("-1\n%d\n",p);
else printf("0\n");
return 0;
}评测结果
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 317276 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 317276 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 317276 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #6: Accepted, time = 31 ms, mem = 317276 KiB, score = 5
测试数据 #7: Accepted, time = 62 ms, mem = 317272 KiB, score = 5
测试数据 #8: Accepted, time = 78 ms, mem = 317272 KiB, score = 5
测试数据 #9: Accepted, time = 124 ms, mem = 317276 KiB, score = 5
测试数据 #10: Accepted, time = 124 ms, mem = 317272 KiB, score = 5
测试数据 #11: Accepted, time = 156 ms, mem = 317272 KiB, score = 5
测试数据 #12: Accepted, time = 187 ms, mem = 317276 KiB, score = 5
测试数据 #13: Accepted, time = 140 ms, mem = 317276 KiB, score = 5
测试数据 #14: Accepted, time = 873 ms, mem = 317272 KiB, score = 5
测试数据 #15: Accepted, time = 1341 ms, mem = 317272 KiB, score = 5
测试数据 #16: Accepted, time = 1700 ms, mem = 317276 KiB, score = 5
测试数据 #17: TimeLimitExceeded, time = 2012 ms, mem = 317276 KiB, score = 0
测试数据 #18: TimeLimitExceeded, time = 2012 ms, mem = 317276 KiB, score = 0
测试数据 #19: TimeLimitExceeded, time = 2012 ms, mem = 317276 KiB, score = 0
TimeLimitExceeded, time = 10867 ms, mem = 317276 KiB, score = 85
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[1000003],p,tot;
int d,s,t;
struct arr{
int w,c;
}tr[1000003*40];int read(){
int f=1,x=0;
char s=getchar();
while(s<'0'||s>'9') s=getchar();
while(s>='0' && s<='9'){
x=x*10+(s-48);
s=getchar();
}
return f*x;
}void push(int num){
tr[2*num].c+=tr[num].c;
tr[2*num+1].c+=tr[num].c;
tr[num].w-=tr[num].c;
tr[num].c=0;
}void build(int num,int l,int r){
if (l==r){
tr[num].w=a[l];
return;
}
build(2*num,l,(l+r)/2);
build(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}int find(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return 2147483647;
if (s<=l && r<=t) return tr[num].w;
return min(find(2*num,l,(l+r)/2),find(2*num+1,(l+r)/2+1,r));
}void insert(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return;
if (s<=l && r<=t){
tr[num].w-=d;
tr[2*num].c+=d;
tr[2*num+1].c+=d;
return;
}
insert(2*num,l,(l+r)/2);
insert(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}int main(){
n=read();m=read();
for (int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
for (int i=1;i<=m;i++){
d=read();s=read();t=read();
if (tot) continue;
int dd=find(1,1,n);
if (dd<d) p=i,tot++;
else insert(1,1,n);
}
if (tot) printf("-1\n%d\n",p);
else printf("0\n");
return 0;
} -
0
线段树 ！！经典模板
http://www.ofsxb.com/archives/455 -
0
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define N 1000010
struct Node{
int flag;
int Min;
}t[N*4];
int n,m;
int A[N];
bool pd=true;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void Pushup(int i)
{
t[i].Min=min(t[i*2].Min,t[i*2+1].Min);
}
void BuildTree(int i,int l,int r)
{
if(l==r)
{
t[i].Min=A[l];
return;
}
int mid=(l+r)/2;
BuildTree(i*2,l,mid);
BuildTree(i*2+1,mid+1,r);
Pushup(i);
}
void Pushdown(int i)
{
if(t[i].flag==0)
return;
t[i*2].Min+=t[i].flag;
t[i*2+1].Min+=t[i].flag;
t[i*2].flag+=t[i].flag;
t[i*2+1].flag+=t[i].flag;
t[i].flag=0;
return;
}
void Updata(int i,int l,int r,int left,int right,int c)
{
if(l>=left&&r<=right)
{
t[i].Min-=c;
t[i].flag-=c;
if(t[i].Min<0)
pd=false;
return;
}
Pushdown(i);
int mid=(l+r)/2;
if(right<=mid)
Updata(i*2,l,mid,left,right,c);
else if(left>mid)
Updata(i*2+1,mid+1,r,left,right,c);
else
{
Updata(i*2,l,mid,left,mid,c);
Updata(i*2+1,mid+1,r,mid+1,right,c);
}
Pushup(i);
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
A[i]=read();
}
BuildTree(1,1,n);
bool haha=false;
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
if(haha)
continue;
Updata(1,1,n,y,z,x);
if(!pd)
{
haha=true;
cout<<"-1"<<endl;
cout<<i<<endl;
}
}
if(pd)
cout<<"0"<<endl;
return 0;
} -
0
#include <bits/stdc++.h> const int MAXN = 1000000 + 5; using namespace std; struct classroom { int need; int start; int end; } crm[MAXN]; int prs[MAXN]; int r[MAXN]; int n, m, sum, ans = 0; int in() { int x = 0, f = 1, c = getchar(); while (!isdigit(c)) { if (c == '-')f = -1; c = getchar(); } while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x * f; } bool judge(int mid) { memset(prs, 0, sizeof(prs)); for (int i = 1; i <= mid; ++i) { prs[crm[i].start] += crm[i].need; prs[crm[i].end + 1] -= crm[i].need; } sum = 0; for (int i = 1; i <= n; ++i) { sum += prs[i]; if (sum > r[i]) { return false; } } return true; } int main() { n = in(); m = in(); for (int i = 1; i <= n; ++i) { r[i] = in(); } for (int i = 1; i <= m; ++i) { crm[i].need = in(); crm[i].start = in(); crm[i].end = in(); } int front = 1, back = m; while (front <= back) { int mid = (front + back) / 2; if (judge(mid)) { front = mid + 1; } else { ans = mid; back = mid - 1; } } if (ans == 0) { printf("0"); } else { printf("-1\n%d", ans); } return 0; }
刷题去
LV 10
@ 2017-07-15 17:13:21
