oj.uz

Submission #536083

# Submission time Handle Problem Language Result Execution time Memory
536083 2022-03-12T09:53:59 Z zaneyu Sandcastle 2 (JOI22_ho_t5) C++14
24 / 100
 5000 ms 856 KB 
/*input
3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-6;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll sub(ll a,ll b){
    ll x=a-b;
    while(x<0) x+=MOD;
    while(x>MOD) x-=MOD;
    return x;
}
ll mult(ll a,ll b){
    return (a*b)%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<(V[i])<<((i!=sz(V)-1)?" ":"\n");
    return out;
}
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2; 
int arr[maxn];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int nxt[maxn];
pii pos[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m;
    cin>>n>>m;
    if(n==1 or m==1){
        m=max(n,m);
        int len=0,pv=-1;
        ll ans=0;
        REP(i,m){
            int x;
            cin>>x;
            if(x>pv) ++len;
            else len=1;
            ans+=len;
            pv=x;
            arr[i]=x;
        }
        len=0,pv=-1;
        for(int i=m-1;i>=0;i--){
            int x=arr[i];
            if(x>pv) ++len;
            else len=1;
            ans+=len;
            pv=x;
        }
        cout<<ans-m;
        return 0;
    }
    REP(i,n) REP(j,m) cin>>arr[i*m+j],pos[i*m+j]={i,j};
    int ans=0;
    REP(i,n){
        REP(j,m){
            int pp=-1;
            REP(k,4){
                int x=i+dx[k],y=j+dy[k];
                if(x<0 or x>=n or y<0 or y>=m) continue;
                if(arr[x*m+y]<=arr[i*m+j] and (pp==-1 or arr[x*m+y]>=arr[pp])) pp=x*m+y;
            } 
            nxt[i*m+j]=pp;
        }
    }
    REP(i,n){
        REP(j,m){
            REP(a,i+1){
                REP(b,j+1){
                    pii p={a,b};
                    for(int x=a;x<=i;x++){
                        for(int y=b;y<=j;y++){
                            if(arr[p.f*m+p.s]<arr[x*m+y]) p={x,y};
                        }
                    }
                    bool wk=1;
                    REP(z,(i-a+1)*(j-b+1)-1){
                        int pp=-1;
                        if(p.f==a or p.f==i or p.s==b or p.s==j){
                            REP(k,4){
                                int x=p.f+dx[k],y=p.s+dy[k];
                                if(x<a or x>i or y<b or y>j) continue;
                                if(arr[x*m+y]<=arr[p.f*m+p.s] and (pp==-1 or arr[x*m+y]>=arr[pp])) pp=x*m+y;
                            }
                        }
                        else{
                            pp=nxt[p.f*m+p.s];
                        }
                        if(pp==-1){
                            wk=0;
                            break;
                        }
                        p=pos[pp];
                        //cout<<pp<<'\n';
                    }
                    //cout<<wk<<' '<<i<<' '<<a<<' '<<j<<' '<<b<<'\n';
                    ans+=wk;
                }
            }
        }
    }
    cout<<ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 684 KB Output is correct
3 Correct 5 ms 852 KB Output is correct
4 Correct 5 ms 856 KB Output is correct
5 Correct 6 ms 856 KB Output is correct
6 Correct 5 ms 856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 509 ms 340 KB Output is correct
10 Correct 1335 ms 344 KB Output is correct
11 Correct 4513 ms 340 KB Output is correct
12 Correct 4265 ms 344 KB Output is correct
13 Correct 665 ms 344 KB Output is correct
14 Correct 270 ms 340 KB Output is correct
15 Correct 622 ms 340 KB Output is correct
16 Correct 552 ms 344 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 509 ms 340 KB Output is correct
10 Correct 1335 ms 344 KB Output is correct
11 Correct 4513 ms 340 KB Output is correct
12 Correct 4265 ms 344 KB Output is correct
13 Correct 665 ms 344 KB Output is correct
14 Correct 270 ms 340 KB Output is correct
15 Correct 622 ms 340 KB Output is correct
16 Correct 552 ms 344 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Execution timed out 5036 ms 468 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 509 ms 340 KB Output is correct
10 Correct 1335 ms 344 KB Output is correct
11 Correct 4513 ms 340 KB Output is correct
12 Correct 4265 ms 344 KB Output is correct
13 Correct 665 ms 344 KB Output is correct
14 Correct 270 ms 340 KB Output is correct
15 Correct 622 ms 340 KB Output is correct
16 Correct 552 ms 344 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Execution timed out 5036 ms 468 KB Time limit exceeded
19 Halted 0 ms 0 KB -