#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
struct node {
int x,y;
long long w;
};
int n,sz;
long long mx[maxn*4];
long long L[maxn*4];
long long R[maxn*4];
long long tree[maxn];
node p[maxn];
map<long long,int> mp;
void add(int x,long long val) {
while(x<=100) {
tree[x] += val;
x += x&-x;
}
}
long long sum(int x) {
int ans = 0;
while(x) {
ans += tree[x];
x -= x&-x;
}
return ans;
}
void update(int pos,int l,int r,int x,long long val) {
if(l>x || r<x) return ;
if(l==r) {
mx[pos] = L[pos] = R[pos] = val;
// printf("pos = %d (%d - %d) : mx = %lld L = %lld R = %lld\n",pos,l,r,mx[pos],L[pos],R[pos]);
return ;
}
int mid = (l+r)/2;
update(pos<<1,l,mid,x,val); update(pos<<1|1,mid+1,r,x,val);
mx[pos] = max(max(mx[pos<<1],mx[pos<<1|1]),max(0LL,R[pos<<1])+max(0LL,L[pos<<1|1]));
L[pos] = L[pos<<1] + ((L[pos<<1]==sum(mid)-sum(l-1)) ? max(0LL,L[pos<<1|1]) : 0);
R[pos] = R[pos<<1|1] + ((R[pos<<1|1]==sum(r)-sum(mid)) ? max(0LL,R[pos<<1]) : 0);
// printf("pos = %d (%d - %d) : mx = %lld L = %lld R = %lld\n",pos,l,r,mx[pos],L[pos],R[pos]);
}
void cpidx() {
int i;
map<long long,int>::iterator it;
for(i=1;i<=n;i++) mp[p[i].x];
for(it=mp.begin();it!=mp.end();++it) it->second = ++sz;
}
main() {
int i;
scanf("%d",&n);
if(n>100) printf("%d",1/0);
for(i=1;i<=n;i++) scanf("%d%d%lld",&p[i].x,&p[i].y,&p[i].w);
cpidx();
for(i=1;i<=n;i++) {
// printf("UPD %d(%d) : %lld\n",p[i].x,mp[p[i].x],p[i].w);
update(1,1,sz,mp[p[i].x],p[i].w);
add(mp[p[i].x],p[i].w);
// printf("-----\n");
}
printf("%lld",max(0LL,mx[1]));
}
Compilation message
bulldozer.cpp:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:52:28: warning: division by zero [-Wdiv-by-zero]
if(n>100) printf("%d",1/0);
~^~
bulldozer.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
bulldozer.cpp:53:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1;i<=n;i++) scanf("%d%d%lld",&p[i].x,&p[i].y,&p[i].w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
