QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#323141	#3797. Wireless Communication Network	socpite	AC ✓	803ms	46768kb	C++23	1.8kb	2024-02-08 18:12:01	2024-02-08 18:12:01

Judging History

你现在查看的是最新测评结果

[2024-02-08 18:12:01]
评测

测评结果：AC
用时：803ms
内存：46768kb

查看

[2024-02-08 18:12:01]
提交

answer

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6+5;
stack<int> stk;

int n;
int ans = 0;

int pfx[maxn], h[maxn];

int st[4*maxn], lz[4*maxn];

void push(int id){
    st[id<<1] += lz[id];
    lz[id<<1] += lz[id];
    
    st[id<<1|1] += lz[id];
    lz[id<<1|1] += lz[id];

    lz[id] = 0;
}

void add(int ql, int qr, int val, int l, int r, int id){
    if(ql > qr)return;
    if(l > qr || ql > r)return;
    if(ql <= l && r <= qr){
        st[id]+=val;
        lz[id]+=val;
    }
    else{
        push(id);
        int mid = (l+r)>>1;
        add(ql, qr, val, l, mid, id<<1);
        add(ql, qr, val, mid+1, r, id<<1|1);
        st[id] = max(st[id<<1], st[id<<1|1]);
    }
}

int gt(int k, int l, int r, int id){
    if(k == 0 || k == n+1)return 0;
    if(l == r)return st[id];
    else {
        push(id);
        int mid = (l+r)>>1;
        if(k <= mid)return gt(k, l, mid, id<<1);
        else return gt(k, mid+1, r, id<<1|1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    stack<int> stk;
    h[0] = h[n+1] = maxn;
    stk.push(0);
    for(int i = 1; i <= n; i++){
        cin >> h[i];
        while(h[stk.top()] < h[i])stk.pop();
        add(stk.top()+1, i-1, 1, 1, n, 1);
        add(i, i, gt(stk.top(), 1, n, 1) + 1, 1, n, 1);
        pfx[i] = st[1]-1;
        stk.push(i);
    }
    memset(st, 0, sizeof(st));
    memset(lz, 0, sizeof(lz));
    while(!stk.empty())stk.pop();
    stk.push(n+1);
    for(int i = n; i > 1; i--){
        while(h[stk.top()] < h[i])stk.pop();
        add(i+1, stk.top()-1, 1, 1, n, 1);
        add(i, i, gt(stk.top(), 1, n, 1) + 1, 1, n, 1);
        ans = max(ans, st[1] + pfx[i-1]);
        stk.push(i);
    }
    cout << ans;
    
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 798ms

memory: 42712kb

input:

output:

result:

ok single line: '91'

Test #2:

score: 0

Accepted

time: 690ms

memory: 42500kb

input:

output:

result:

ok single line: '95'

Test #3:

score: 0

Accepted

time: 790ms

memory: 42596kb

input:

output:

result:

ok single line: '94'

Test #4:

score: 0

Accepted

time: 785ms

memory: 42732kb

input:

output:

result:

ok single line: '94'

Test #5:

score: 0

Accepted

time: 791ms

memory: 42932kb

input:

output:

result:

ok single line: '99'

Test #6:

score: 0

Accepted

time: 787ms

memory: 42632kb

input:

output:

result:

ok single line: '92'

Test #7:

score: 0

Accepted

time: 795ms

memory: 42608kb

input:

output:

result:

ok single line: '92'

Test #8:

score: 0

Accepted

time: 692ms

memory: 46768kb

input:

output:

result:

ok single line: '999996'

Test #9:

score: 0

Accepted

time: 695ms

memory: 46280kb

input:

output:

result:

ok single line: '999997'

Test #10:

score: 0

Accepted

time: 0ms

memory: 38832kb

input:

output:

result:

ok single line: '2'

Test #11:

score: 0

Accepted

time: 0ms

memory: 36940kb

input:

output:

result:

ok single line: '2'

Test #12:

score: 0

Accepted

time: 0ms

memory: 37192kb

input:

output:

result:

ok single line: '2'

Test #13:

score: 0

Accepted

time: 0ms

memory: 38332kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 0ms

memory: 38812kb

input:

output:

result:

ok single line: '2'

Test #15:

score: 0

Accepted

time: 0ms

memory: 37476kb

input:

output:

result:

ok single line: '2'

Test #16:

score: 0

Accepted

time: 0ms

memory: 39056kb

input:

output:

result:

ok single line: '3'

Test #17:

score: 0

Accepted

time: 0ms

memory: 37032kb

input:

output:

result:

ok single line: '3'

Test #18:

score: 0

Accepted

time: 0ms

memory: 38420kb

input:

output:

result:

ok single line: '3'

Test #19:

score: 0

Accepted

time: 4ms

memory: 38404kb

input:

output:

result:

ok single line: '3'

Test #20:

score: 0

Accepted

time: 4ms

memory: 38292kb

input:

output:

result:

ok single line: '3'

Test #21:

score: 0

Accepted

time: 0ms

memory: 38104kb

input:

output:

result:

ok single line: '3'

Test #22:

score: 0

Accepted

time: 3ms

memory: 37544kb

input:

output:

result:

ok single line: '3'

Test #23:

score: 0

Accepted

time: 0ms

memory: 37404kb

input:

output:

result:

ok single line: '3'

Test #24:

score: 0

Accepted

time: 4ms

memory: 38040kb

input:

output:

result:

ok single line: '3'

Test #25:

score: 0

Accepted

time: 0ms

memory: 37852kb

input:

output:

result:

ok single line: '3'

Test #26:

score: 0

Accepted

time: 3ms

memory: 37924kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 0ms

memory: 38612kb

input:

output:

result:

ok single line: '3'

Test #28:

score: 0

Accepted

time: 0ms

memory: 38528kb

input:

output:

result:

ok single line: '3'

Test #29:

score: 0

Accepted

time: 0ms

memory: 38832kb

input:

output:

result:

ok single line: '3'

Test #30:

score: 0

Accepted

time: 6ms

memory: 38932kb

input:

output:

result:

ok single line: '3'

Test #31:

score: 0

Accepted

time: 4ms

memory: 38696kb

input:

output:

result:

ok single line: '3'

Test #32:

score: 0

Accepted

time: 0ms

memory: 37936kb

input:

output:

result:

ok single line: '3'

Test #33:

score: 0

Accepted

time: 0ms

memory: 38472kb

input:

output:

result:

ok single line: '3'

Test #34:

score: 0

Accepted

time: 6ms

memory: 37964kb

input:

output:

result:

ok single line: '3'

Test #35:

score: 0

Accepted

time: 4ms

memory: 38844kb

input:

output:

result:

ok single line: '3'

Test #36:

score: 0

Accepted

time: 0ms

memory: 37476kb

input:

output:

result:

ok single line: '3'

Test #37:

score: 0

Accepted

time: 0ms

memory: 38652kb

input:

output:

result:

ok single line: '3'

Test #38:

score: 0

Accepted

time: 3ms

memory: 37128kb

input:

output:

result:

ok single line: '3'

Test #39:

score: 0

Accepted

time: 4ms

memory: 38852kb

input:

output:

result:

ok single line: '3'

Test #40:

score: 0

Accepted

time: 0ms

memory: 38244kb

input:

output:

result:

ok single line: '4'

Test #41:

score: 0

Accepted

time: 6ms

memory: 37444kb

input:

output:

result:

ok single line: '4'

Test #42:

score: 0

Accepted

time: 0ms

memory: 36860kb

input:

output:

result:

ok single line: '4'

Test #43:

score: 0

Accepted

time: 3ms

memory: 38268kb

input:

output:

result:

ok single line: '4'

Test #44:

score: 0

Accepted

time: 0ms

memory: 38012kb

input:

output:

result:

ok single line: '4'

Test #45:

score: 0

Accepted

time: 0ms

memory: 37536kb

input:

output:

result:

ok single line: '4'

Test #46:

score: 0

Accepted

time: 0ms

memory: 39148kb

input:

output:

result:

ok single line: '4'

Test #47:

score: 0

Accepted

time: 0ms

memory: 37668kb

input:

output:

result:

ok single line: '3'

Test #48:

score: 0

Accepted

time: 4ms

memory: 38188kb

input:

output:

result:

ok single line: '4'

Test #49:

score: 0

Accepted

time: 0ms

memory: 38412kb

input:

output:

result:

ok single line: '4'

Test #50:

score: 0

Accepted

time: 6ms

memory: 38324kb

input:

output:

result:

ok single line: '4'

Test #51:

score: 0

Accepted

time: 0ms

memory: 38204kb

input:

output:

result:

ok single line: '4'

Test #52:

score: 0

Accepted

time: 4ms

memory: 38604kb

input:

output:

result:

ok single line: '4'

Test #53:

score: 0

Accepted

time: 4ms

memory: 37216kb

input:

output:

result:

ok single line: '3'

Test #54:

score: 0

Accepted

time: 6ms

memory: 38744kb

input:

output:

result:

ok single line: '4'

Test #55:

score: 0

Accepted

time: 4ms

memory: 37088kb

input:

output:

result:

ok single line: '3'

Test #56:

score: 0

Accepted

time: 0ms

memory: 38772kb

input:

output:

result:

ok single line: '4'

Test #57:

score: 0

Accepted

time: 0ms

memory: 37868kb

input:

output:

result:

ok single line: '4'

Test #58:

score: 0

Accepted

time: 0ms

memory: 39064kb

input:

output:

result:

ok single line: '4'

Test #59:

score: 0

Accepted

time: 4ms

memory: 38668kb

input:

output:

result:

ok single line: '3'

Test #60:

score: 0

Accepted

time: 3ms

memory: 38028kb

input:

output:

result:

ok single line: '4'

Test #61:

score: 0

Accepted

time: 0ms

memory: 38852kb

input:

output:

result:

ok single line: '3'

Test #62:

score: 0

Accepted

time: 0ms

memory: 38952kb

input:

output:

result:

ok single line: '4'

Test #63:

score: 0

Accepted

time: 0ms

memory: 38168kb

input:

output:

result:

ok single line: '4'

Test #64:

score: 0

Accepted

time: 4ms

memory: 38436kb

input:

output:

result:

ok single line: '4'

Test #65:

score: 0

Accepted

time: 4ms

memory: 37924kb

input:

output:

result:

ok single line: '4'

Test #66:

score: 0

Accepted

time: 4ms

memory: 37884kb

input:

output:

result:

ok single line: '4'

Test #67:

score: 0

Accepted

time: 0ms

memory: 37648kb

input:

output:

result:

ok single line: '4'

Test #68:

score: 0

Accepted

time: 4ms

memory: 38232kb

input:

output:

result:

ok single line: '4'

Test #69:

score: 0

Accepted

time: 4ms

memory: 37352kb

input:

output:

result:

ok single line: '4'

Test #70:

score: 0

Accepted

time: 3ms

memory: 37184kb

input:

output:

result:

ok single line: '4'

Test #71:

score: 0

Accepted

time: 0ms

memory: 38588kb

input:

output:

result:

ok single line: '3'

Test #72:

score: 0

Accepted

time: 0ms

memory: 38756kb

input:

output:

result:

ok single line: '4'

Test #73:

score: 0

Accepted

time: 0ms

memory: 37880kb

input:

output:

result:

ok single line: '4'

Test #74:

score: 0

Accepted

time: 0ms

memory: 37224kb

input:

output:

result:

ok single line: '4'

Test #75:

score: 0

Accepted

time: 0ms

memory: 36948kb

input:

output:

result:

ok single line: '4'

Test #76:

score: 0

Accepted

time: 4ms

memory: 38336kb

input:

output:

result:

ok single line: '4'

Test #77:

score: 0

Accepted

time: 3ms

memory: 38252kb

input:

output:

result:

ok single line: '3'

Test #78:

score: 0

Accepted

time: 6ms

memory: 38224kb

input:

output:

result:

ok single line: '4'

Test #79:

score: 0

Accepted

time: 0ms

memory: 38848kb

input:

output:

result:

ok single line: '3'

Test #80:

score: 0

Accepted

time: 0ms

memory: 36968kb

input:

output:

result:

ok single line: '4'

Test #81:

score: 0

Accepted

time: 0ms

memory: 37268kb

input:

output:

result:

ok single line: '4'

Test #82:

score: 0

Accepted

time: 4ms

memory: 37548kb

input:

output:

result:

ok single line: '4'

Test #83:

score: 0

Accepted

time: 0ms

memory: 37048kb

input:

output:

result:

ok single line: '3'

Test #84:

score: 0

Accepted

time: 0ms

memory: 37576kb

input:

output:

result:

ok single line: '4'

Test #85:

score: 0

Accepted

time: 0ms

memory: 37568kb

input:

output:

result:

ok single line: '3'

Test #86:

score: 0

Accepted

time: 0ms

memory: 37456kb

input:

output:

result:

ok single line: '4'

Test #87:

score: 0

Accepted

time: 4ms

memory: 38320kb

input:

output:

result:

ok single line: '4'

Test #88:

score: 0

Accepted

time: 0ms

memory: 38776kb

input:

output:

result:

ok single line: '4'

Test #89:

score: 0

Accepted

time: 3ms

memory: 37240kb

input:

output:

result:

ok single line: '4'

Test #90:

score: 0

Accepted

time: 0ms

memory: 38800kb

input:

output:

result:

ok single line: '4'

Test #91:

score: 0

Accepted

time: 4ms

memory: 36936kb

input:

output:

result:

ok single line: '4'

Test #92:

score: 0

Accepted

time: 0ms

memory: 37408kb

input:

output:

result:

ok single line: '4'

Test #93:

score: 0

Accepted

time: 3ms

memory: 37200kb

input:

output:

result:

ok single line: '4'

Test #94:

score: 0

Accepted

time: 0ms

memory: 37856kb

input:

output:

result:

ok single line: '4'

Test #95:

score: 0

Accepted

time: 3ms

memory: 37108kb

input:

output:

result:

ok single line: '4'

Test #96:

score: 0

Accepted

time: 0ms

memory: 38228kb

input:

output:

result:

ok single line: '4'

Test #97:

score: 0

Accepted

time: 0ms

memory: 37772kb

input:

output:

result:

ok single line: '4'

Test #98:

score: 0

Accepted

time: 0ms

memory: 38288kb

input:

output:

result:

ok single line: '4'

Test #99:

score: 0

Accepted

time: 0ms

memory: 38544kb

input:

output:

result:

ok single line: '4'

Test #100:

score: 0

Accepted

time: 0ms

memory: 37696kb

input:

output:

result:

ok single line: '4'

Test #101:

score: 0

Accepted

time: 0ms

memory: 37012kb

input:

output:

result:

ok single line: '3'

Test #102:

score: 0

Accepted

time: 0ms

memory: 38312kb

input:

output:

result:

ok single line: '4'

Test #103:

score: 0

Accepted

time: 3ms

memory: 37112kb

input:

output:

result:

ok single line: '3'

Test #104:

score: 0

Accepted

time: 0ms

memory: 37860kb

input:

output:

result:

ok single line: '4'

Test #105:

score: 0

Accepted

time: 0ms

memory: 38932kb

input:

output:

result:

ok single line: '4'

Test #106:

score: 0

Accepted

time: 3ms

memory: 37680kb

input:

output:

result:

ok single line: '4'

Test #107:

score: 0

Accepted

time: 0ms

memory: 37088kb

input:

output:

result:

ok single line: '3'

Test #108:

score: 0

Accepted

time: 0ms

memory: 38988kb

input:

output:

result:

ok single line: '4'

Test #109:

score: 0

Accepted

time: 6ms

memory: 38864kb

input:

output:

result:

ok single line: '3'

Test #110:

score: 0

Accepted

time: 0ms

memory: 37972kb

input:

output:

result:

ok single line: '4'

Test #111:

score: 0

Accepted

time: 0ms

memory: 37008kb

input:

output:

result:

ok single line: '4'

Test #112:

score: 0

Accepted

time: 3ms

memory: 38200kb

input:

output:

result:

ok single line: '4'

Test #113:

score: 0

Accepted

time: 0ms

memory: 38128kb

input:

output:

result:

ok single line: '4'

Test #114:

score: 0

Accepted

time: 0ms

memory: 38804kb

input:

output:

result:

ok single line: '4'

Test #115:

score: 0

Accepted

time: 0ms

memory: 37116kb

input:

output:

result:

ok single line: '4'

Test #116:

score: 0

Accepted

time: 4ms

memory: 37232kb

input:

output:

result:

ok single line: '4'

Test #117:

score: 0

Accepted

time: 0ms

memory: 37508kb

input:

output:

result:

ok single line: '4'

Test #118:

score: 0

Accepted

time: 0ms

memory: 38084kb

input:

output:

result:

ok single line: '4'

Test #119:

score: 0

Accepted

time: 0ms

memory: 38336kb

input:

output:

result:

ok single line: '4'

Test #120:

score: 0

Accepted

time: 4ms

memory: 36908kb

input:

output:

result:

ok single line: '4'

Test #121:

score: 0

Accepted

time: 0ms

memory: 38656kb

input:

output:

result:

ok single line: '4'

Test #122:

score: 0

Accepted

time: 0ms

memory: 37616kb

input:

output:

result:

ok single line: '4'

Test #123:

score: 0

Accepted

time: 0ms

memory: 38612kb

input:

output:

result:

ok single line: '4'

Test #124:

score: 0

Accepted

time: 0ms

memory: 38820kb

input:

output:

result:

ok single line: '4'

Test #125:

score: 0

Accepted

time: 0ms

memory: 37840kb

input:

output:

result:

ok single line: '4'

Test #126:

score: 0

Accepted

time: 3ms

memory: 37344kb

input:

output:

result:

ok single line: '4'

Test #127:

score: 0

Accepted

time: 4ms

memory: 38876kb

input:

output:

result:

ok single line: '4'

Test #128:

score: 0

Accepted

time: 0ms

memory: 37892kb

input:

output:

result:

ok single line: '4'

Test #129:

score: 0

Accepted

time: 0ms

memory: 38968kb

input:

output:

result:

ok single line: '4'

Test #130:

score: 0

Accepted

time: 0ms

memory: 38604kb

input:

output:

result:

ok single line: '4'

Test #131:

score: 0

Accepted

time: 4ms

memory: 38588kb

input:

output:

result:

ok single line: '3'

Test #132:

score: 0

Accepted

time: 4ms

memory: 37420kb

input:

output:

result:

ok single line: '4'

Test #133:

score: 0

Accepted

time: 0ms

memory: 38632kb

input:

output:

result:

ok single line: '3'

Test #134:

score: 0

Accepted

time: 0ms

memory: 38408kb

input:

output:

result:

ok single line: '4'

Test #135:

score: 0

Accepted

time: 0ms

memory: 38332kb

input:

output:

result:

ok single line: '4'

Test #136:

score: 0

Accepted

time: 0ms

memory: 38104kb

input:

output:

result:

ok single line: '4'

Test #137:

score: 0

Accepted

time: 9ms

memory: 37740kb

input:

output:

result:

ok single line: '4'

Test #138:

score: 0

Accepted

time: 6ms

memory: 38668kb

input:

output:

result:

ok single line: '4'

Test #139:

score: 0

Accepted

time: 4ms

memory: 38332kb

input:

output:

result:

ok single line: '4'

Test #140:

score: 0

Accepted

time: 0ms

memory: 38316kb

input:

output:

result:

ok single line: '4'

Test #141:

score: 0

Accepted

time: 3ms

memory: 37820kb

input:

output:

result:

ok single line: '4'

Test #142:

score: 0

Accepted

time: 4ms

memory: 37108kb

input:

output:

result:

ok single line: '4'

Test #143:

score: 0

Accepted

time: 3ms

memory: 37480kb

input:

output:

result:

ok single line: '4'

Test #144:

score: 0

Accepted

time: 0ms

memory: 37220kb

input:

output:

result:

ok single line: '4'

Test #145:

score: 0

Accepted

time: 0ms

memory: 37584kb

input:

output:

result:

ok single line: '4'

Test #146:

score: 0

Accepted

time: 0ms

memory: 37512kb

input:

output:

result:

ok single line: '4'

Test #147:

score: 0

Accepted

time: 4ms

memory: 36880kb

input:

output:

result:

ok single line: '4'

Test #148:

score: 0

Accepted

time: 6ms

memory: 38680kb

input:

output:

result:

ok single line: '4'

Test #149:

score: 0

Accepted

time: 0ms

memory: 38472kb

input:

output:

result:

ok single line: '4'

Test #150:

score: 0

Accepted

time: 4ms

memory: 37612kb

input:

output:

result:

ok single line: '4'

Test #151:

score: 0

Accepted

time: 0ms

memory: 38004kb

input:

output:

result:

ok single line: '4'

Test #152:

score: 0

Accepted

time: 0ms

memory: 37856kb

input:

output:

result:

ok single line: '4'

Test #153:

score: 0

Accepted

time: 0ms

memory: 38116kb

input:

output:

result:

ok single line: '4'

Test #154:

score: 0

Accepted

time: 0ms

memory: 37728kb

input:

output:

result:

ok single line: '4'

Test #155:

score: 0

Accepted

time: 0ms

memory: 37604kb

input:

output:

result:

ok single line: '4'

Test #156:

score: 0

Accepted

time: 0ms

memory: 37500kb

input:

output:

result:

ok single line: '4'

Test #157:

score: 0

Accepted

time: 6ms

memory: 38676kb

input:

output:

result:

ok single line: '4'

Test #158:

score: 0

Accepted

time: 4ms

memory: 36836kb

input:

output:

result:

ok single line: '4'

Test #159:

score: 0

Accepted

time: 0ms

memory: 38472kb

input:

output:

result:

ok single line: '4'

Test #160:

score: 0

Accepted

time: 793ms

memory: 42856kb

input:

output:

result:

ok single line: '95'

Test #161:

score: 0

Accepted

time: 793ms

memory: 42700kb

input:

output:

result:

ok single line: '89'

Test #162:

score: 0

Accepted

time: 782ms

memory: 42704kb

input:

output:

result:

ok single line: '92'

Test #163:

score: 0

Accepted

time: 803ms

memory: 42584kb

input:

output:

result:

ok single line: '90'