?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
242192715 |
Дорешивание: BARBARIANNNNN |
1117G - 12 | C++20 (GCC 11-64) | Полное решение | 3618 мс | 87184 КБ | 2024-01-18 14:05:49 | 2024-01-18 14:05:49 |
#include<bits/stdc++.h> using namespace std; int n,m,a[1000005]; int top,st[1000005]; vector<int>g[1000005]; long long c[2][1000005]; int l[1000005],r[1000005]; void add(int t,int x,int v) { while(x<=n+3) { c[t][x]+=v; x+=(x&-x); } } long long qry(int t,int x) { long long s=0; while(x) { s+=c[t][x]; x-=(x&-x); } return s; } long long ans[1000005]; void solve() { for(int i=1; i<=n; i++) { g[i].clear(); } memset(c,0,sizeof(c)); for(int i=1; i<=m; i++) { g[l[i]].push_back(i); } st[top=0]=n+1; for(int i=n; i>=1; i--) { while(top&&a[st[top]]<a[i])top--; add(0,i,-i+1); add(0,st[top],i-1); add(1,i,1); add(1,st[top],-1); add(0,st[top],st[top]-i); st[++top]=i; for(int x:g[i]) { ans[x]+=qry(0,r[x])+r[x]*qry(1,r[x]); } } } int main() { 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",&l[i]); } for(int i=1; i<=m; i++) { scanf("%d",&r[i]); } solve(); for(int i=1; i<=m; i++) { l[i]=n-l[i]+1; r[i]=n-r[i]+1; swap(l[i],r[i]); } reverse(a+1,a+n+1); solve(); for(int i=1; i<=m; i++) { printf("%lld ",ans[i]-(r[i]-l[i]+1)); } return 0; }
?
?
?
?