QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #739759 | #1191. Reordering the Documents | shstyle | ML | 163ms | 232920kb | C++23 | 2.8kb | 2024-11-12 22:59:19 | 2024-11-12 22:59:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=3050,mod=1e9+7;
typedef long long ll;
typedef pair<ll,ll> PII;
int n,m,k;
int a[N];
typedef struct{
int l,r,len;
ll sum;
ll tag1,tag2;
}Node;
Node tr[N][N<<2];
void pushup(Node tr[],int u){
tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%mod;
}
void pushdown(Node tr[],int u){
if(tr[u].tag2!=-1){
tr[u].tag1=0;
tr[u<<1].sum=tr[u].tag2*tr[u<<1].len%mod;tr[u<<1].tag2=tr[u].tag2;
tr[u<<1|1].sum=tr[u].tag2*tr[u<<1|1].len%mod;tr[u<<1|1].tag2=tr[u].tag2;
tr[u].tag2=-1;
}
if(tr[u].tag1!=0){
tr[u<<1].sum+=tr[u].tag1*tr[u<<1].len%mod;tr[u<<1].tag1=(tr[u<<1].tag1+tr[u].tag1)%mod;
tr[u<<1|1].sum+=tr[u].tag1*tr[u<<1|1].len%mod;tr[u<<1|1].tag1=(tr[u<<1|1].tag1+tr[u].tag1)%mod;
tr[u].tag1=0;
}
}
void build(Node tr[],int u,int l,int r){
tr[u]={l,r,r-l+1,0,0,-1};
if(l==r){
return;
}else{
int mid=l+r>>1;
build(tr,u<<1,l,mid);
build(tr,u<<1|1,mid+1,r);
pushup(tr,u);
}
}
void modify(Node tr[],int u,int l,int r,ll c,ll type){
if(tr[u].l>=l&&tr[u].r<=r){
if(type==1){
tr[u].tag1=(tr[u].tag1+c)%mod;
tr[u].sum=(tr[u].sum+c*tr[u].len)%mod;
}else{
tr[u].tag2=c;
tr[u].sum=c*tr[u].len%mod;
}
}else{
int mid=tr[u].l+tr[u].r>>1;
pushdown(tr,u);
if(l<=mid) modify(tr,u<<1,l,r,c,type);
if(r>mid) modify(tr,u<<1|1,l,r,c,type);
pushup(tr,u);
}
}
ll query(Node tr[],int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u].sum;
}else{
int mid=tr[u].l+tr[u].r>>1;
pushdown(tr,u);
ll sum=0;
if(l<=mid) sum+=query(tr,u<<1,l,r);
if(r>mid) sum+=query(tr,u<<1|1,l,r);
return sum%mod;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[0]=1;
for(int i=1;i<=n;i++) a[i]++;
for(int i=0;i<=n+1;i++) build(tr[i],1,1,n+1);
modify(tr[1],1,1,1,1,1);
for(int i=1;i<=n;i++){
vector<array<ll,3>> v;
for(int j=0;j<i;j++){
int len=j+1;
array<ll,3> a3={i-j,a[i-1],query(tr[len],1,1,a[i])};
v.push_back(a3);
}
if(a[i]<a[i-1]){
for(int j=1;j<=n+1;j++) modify(tr[j],1,1,n+1,0,2);
}
for(auto [x,y,z]:v){
modify(tr[x],1,y,y,z,1);
}
}
ll ans=0;
for(int i=1;i<=n+1;i++){
// for(int j=1;j<=n+1;j++){
int rl=i-1;
if(max(rl,n-rl)<=m){
// cout<<rl<<" "<<n-rl<<" "<<tr[i][1].sum<<endl;
ans=(ans+tr[i][1].sum)%mod;
}
// }
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7772kb
input:
6 3 1 3 4 2 6 5
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7804kb
input:
6 6 1 3 4 2 6 5
output:
8
result:
ok answer is '8'
Test #3:
score: 0
Accepted
time: 0ms
memory: 8032kb
input:
4 4 4 3 1 2
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 8024kb
input:
6 3 1 3 4 2 6 5
output:
4
result:
ok answer is '4'
Test #5:
score: 0
Accepted
time: 1ms
memory: 7844kb
input:
6 6 1 3 4 2 6 5
output:
8
result:
ok answer is '8'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
4 4 4 3 1 2
output:
0
result:
ok answer is '0'
Test #7:
score: 0
Accepted
time: 139ms
memory: 227816kb
input:
1000 500 4 5 6 8 10 11 12 13 14 15 20 23 25 26 28 29 33 35 1 2 36 38 3 7 41 9 16 44 48 17 18 51 52 53 19 21 54 22 24 59 61 62 27 67 30 31 32 34 68 69 37 39 73 40 76 77 42 81 83 43 85 45 87 46 89 94 47 95 49 50 97 101 55 103 105 56 57 58 106 60 108 110 63 111 114 64 115 65 119 66 70 71 120 121 72 124...
output:
11363968
result:
ok answer is '11363968'
Test #8:
score: 0
Accepted
time: 163ms
memory: 232920kb
input:
1000 500 1 3 5 7 8 11 12 13 15 18 19 21 25 26 28 30 32 2 4 6 34 9 36 37 10 38 39 14 41 43 44 16 45 17 20 22 46 50 52 23 53 54 24 55 57 27 29 58 61 31 63 64 33 35 66 40 69 42 72 73 47 48 49 51 76 77 80 56 81 59 83 60 62 65 84 67 68 85 70 71 74 87 75 78 79 88 82 86 93 95 89 96 90 97 91 92 94 103 106 9...
output:
809753703
result:
ok answer is '809753703'
Test #9:
score: -100
Memory Limit Exceeded
input:
1000 500 1 2 4 5 6 7 8 12 13 14 17 22 23 24 27 30 31 33 34 37 38 42 45 46 47 48 49 50 51 52 54 57 58 61 63 64 66 67 68 69 76 78 79 81 82 83 84 90 91 92 93 95 97 98 3 9 10 11 15 16 99 105 18 106 108 109 19 20 21 25 26 28 113 118 123 29 32 129 133 35 134 36 39 40 135 41 137 43 142 44 143 145 147 53 55...
output:
292864