QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#405104 | #8229. 栈 | dingdingtang11514# | 0 | 32ms | 7884kb | C++14 | 3.1kb | 2024-05-05 11:22:46 | 2024-05-05 11:22:46 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
// #include <bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define Grf(it,u,to) for(int it=he[u],to;(to=e[it],it);it=nxt[it])
#define In __inline
#define OP operator
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace Mine {
// mt19937_64 wql(514);
In int read() {
ll x=1,a=0;
char ch=getchar();
while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
return a*x;
} const int N=1e5+100;
int n,m;
namespace S0 {
struct stk {
int sts[5005],stv[5005],tot;
void push(int val,int sum) {sts[++tot]=sum,stv[tot]=val;}
void pp(int cnt) {
while(tot && sts[tot]<=cnt) cnt-=sts[tot--];
if(tot) sts[tot]-=cnt;
} In int get(int p) {
int ret=0,i=1; while(i<=tot && p>=sts[i]) {
p-=sts[i];ret+=sts[i]*stv[i];i++;
} if(i<=tot) ret+=stv[i]*p;
return ret;
} In int get(int l,int r){
return get(r)-get(l-1);
} void print() {
For(i,1,tot) printf("%lld ",sts[i]);
puts("");
}
} mp[5005];
void solve0() {
while(m--) {
// printf("%d :\n",m);
int opt=read(); if(opt==1) {
int l=read(),r=read(),x=read(),y=read();
For(i,l,r) mp[i].push(y,x);
} else if(opt==2) {
int l=read(),r=read(),x=read();
For(i,l,r) mp[i].pp(x);
} else {
int x=read(),l=read(),r=read();
printf("%lld\n",mp[x].get(l,r));
} //For(i,1,n) mp[i].print();
// puts("");
}
}
} namespace S1 {
struct node{
int x=0,y=0; /// a_i = max ( x , a_i + y )
} tr[N<<2];
void pushdown(int u) {
int X=tr[u].x,Y=tr[u].y;
tr[u<<1].x+=X,tr[u<<1|1].x+=X;
tr[u<<1].y=max(tr[u<<1].y+X,Y);
tr[u<<1|1].y=max(tr[u<<1|1].y+X,Y);
tr[u].x=tr[u].y=0;
}
void mdf(int ql,int qr,int val,int u=1,int l=1,int r=n) {
if(ql<=l && r<=qr) tr[u].x+=val,tr[u].y=0;
else { int mid=(l+r)>>1; pushdown(u);
if(ql<=mid) mdf(ql,qr,val,u<<1,l,mid);
if(mid<qr) mdf(ql,qr,val,u<<1|1,mid+1,r);
}
} int ask(int pos,int u=1,int l=1,int r=n) {
if(l==r) return max(0+tr[u].x,tr[u].y);
int mid=(l+r)>>1; pushdown(u);
if(pos<=mid) return ask(pos,u<<1,l,mid);
return ask(pos,u<<1|1,mid+1,r);
}
void solve1() {
while(m--) {
// printf("%d :\n",m);
int opt=read(); if(opt==1) {
int l=read(),r=read(),x=read(),y=read();
mdf(l,r,x);
} else if(opt==2) {
int l=read(),r=read(),x=read();
mdf(l,r,-x);
} else {
int x=read(),l=read(),r=read();
int siz=ask(x);
printf("%lld\n",min(siz,r)-min(siz,l-1));
} //For(i,1,n) printf("%lld ",ask(i));
// putsa("");
}
}
}
signed main() {
n=read(),m=read();
// if(n<=5000 && m<=5000) S0::solve0();
// else S1::solve1();
S1::solve1();
return 0;
}
}signed main() {
// freopen("homework.in","r",stdin);
// freopen("homework.out","w",stdout);
return Mine::main();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 4036kb
input:
4907 4910 2 763 3330 1 3 307 1 1 1 2262 3430 22699 89397 1 1915 4000 51541 67587 2 212 2990 9763 2 1086 2162 1 2 1813 4496 16760 1 51 2796 68005 99390 1 1267 1519 74236 66178 3 1768 23808 54314 2 900 4122 27758 3 3287 17350 28989 2 3277 4024 3633 2 444 4866 1 2 353 4219 1061 1 987 3141 99906 17320 2...
output:
0 30507 11640 5275 3437 0 25911 0 1146 0 0 0 0 13060 0 7846 0 130450 0 22042 101132 24302 17557 2850 162970 0 9062 0 7845 85303 108469 0 0 45427 130254 48754 0 0 51519 11465 7399 0 81716 53555 0 0 14394 0 4218 0 11391 3958 86292 0 35736 5369 0 0 0 49479 1179 4534 16295 15596 18833 42042 17557 10253 ...
result:
wrong answer 2nd numbers differ - expected: '3032090730', found: '30507'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 32ms
memory: 7832kb
input:
99999 99998 1 5026 18575 27178 90423 3 30623 1 1 3 76936 1 1 1 77021 95683 84664 24734 1 46085 74886 40512 11266 3 5048 8594 22468 1 53318 77721 97151 70784 1 70645 91192 37556 13013 1 56752 56940 91812 62887 1 7928 34576 87339 69404 3 74875 32807 100970 3 22338 17221 25771 3 21421 20602 57957 3 717...
output:
0 0 13875 68164 8551 37356 51678 78688 9772 17674 28663 11002 102350 18755 36993 229473 61114 309657 445575 67332 280040 41468 565383 14241 245087 151356 35296 139339 108738 174373 21036 290401 205700 405809 35460 43749 209279 494612 42184 624800 245616 672241 71368 774313 1002309 259392 236613 8906...
result:
wrong answer 3rd numbers differ - expected: '1254619125', found: '13875'
Subtask #3:
score: 0
Wrong Answer
Test #12:
score: 0
Wrong Answer
time: 24ms
memory: 7844kb
input:
100000 99993 1 47773 70467 16065 1 2 52349 78446 2304 3 40821 1 1 1 40216 93069 78144 1 1 41089 43671 76025 1 2 35263 68629 31066 3 79881 13534 57327 3 5556 1 1 2 21962 38192 1 1 664 58116 9417 1 3 28089 6039 7989 2 88500 90302 9946 3 63215 49410 60770 2 11069 89527 57581 2 70303 97603 12363 1 3420 ...
output:
0 43794 0 1951 11361 129 898 29245 7969 0 34972 16405 59952 123666 24537 68209 34537 0 32225 32066 0 26333 16824 96178 14285 245288 57614 1602 114570 61935 4068 65762 17609 152949 26099 179359 250368 2323 183349 125791 17414 61871 0 0 0 183297 23029 54464 0 26259 204595 35604 0 0 18437 0 0 0 138046 ...
result:
wrong answer 10th numbers differ - expected: '1947', found: '0'
Subtask #4:
score: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 28ms
memory: 7884kb
input:
99999 99996 3 77889 1 10000000000 1 6316 86327 89644 386 3 9260 1 10000000000 2 2603 47234 69717 2 20260 73011 19290 2 62477 81233 26127 1 50140 68508 37004 98794 2 14449 22788 16063 1 43860 84932 50375 21777 1 67345 94584 28202 66610 2 661 68654 1 1 14411 94422 82738 61196 1 16563 94416 4920 38408 ...
output:
0 89644 0 0 586692 52542 0 77150 77150 105774 77150 0 0 63627 107367 71244 0 220294 68770 41680 58519 108806 0 84171 37494 0 0 262388 189704 0 183158 0 330620 266786 200713 6281 292978 0 99905 0 0 0 35935 170639 48307 152865 0 114736 0 0 0 0 102049 0 92045 270432 205670 0 0 81804 271323 35933 22901 ...
result:
wrong answer 2nd numbers differ - expected: '34602584', found: '89644'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%