Submission #64339

#	Time	Username	Problem	Language	Result	Execution time	Memory
64339		knon0501	조화행렬 (KOI18_matrix)	C++14	0 / 100	768 ms	37516 KiB

matrix

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n,m;
const int MX=2e5+5;
pair<int,pair<int,int>> a[MX];
unordered_map<long long,int> seg;
unordered_map<int,int> xx;
unordered_map<int,int> yy;
long long nn;
int ans;
int p;
unordered_map<long long,long long> lazy;
inline int g(int y,int lev1){
    stack<int> S;
    S.push(1);
    S.push(nn);
    S.push(1);
    int k=0;
    int lv,r,l;
    long long t;
    int rr;
    while(!S.empty()){
        lv=S.top();S.pop();
        r=S.top();S.pop();
        l=S.top();S.pop();
        t=lazy[nn*2*lev1+lv];
        rr=(t%n>=(r+l)/2);
        if(t>0 && r>l){
            seg[nn*2*lev1+lv*2+rr]=max(seg[nn*2*lev1+lv*2+rr],(int)(t/n));
            lazy[nn*2*lev1+lv*2+rr]=t;
        }
        if(l>=y)continue;
        if(r<y)k=max(k,seg[nn*2*lev1+lv]);
        else{
            S.push(l);
            S.push((l+r)/2);
            S.push(lv*2);
            S.push((l+r)/2+1);
            S.push(r);
            S.push(lv*2+1);
        }
        if(k==ans)return ans;
    }
    return k;
}
inline int f(int x,int y){
    stack<int> S;
    S.push(1);
    S.push(nn);
    S.push(1);
    int k=0;
    int lv,r,l;
    while(!S.empty()){
        lv=S.top();S.pop();
        r=S.top();S.pop();
        l=S.top();S.pop();

        if(l>=x)continue;
        if(r<x)k=max(k,g(y,lv));
        else{
            S.push(l);
            S.push((l+r)/2);
            S.push(lv*2);
            S.push((l+r)/2+1);
            S.push(r);
            S.push(lv*2+1);
        }
    }
    return k;
}
void process(){
    int i,j;
    for(nn=1 ; nn<n ; nn*=2);
    for(i=1 ; i<=n ; i++)cin>>a[i].f;
    for(i=1 ; i<=n ; i++)cin>>a[i].s.f;
    for(i=1 ; i<=n ; i++)cin>>a[i].s.s;
    sort(a+1,a+n+1);
    set<int> S1;
    set<int> S2;
    for(i=1 ; i<=n ; i++){
        S1.insert(a[i].s.f);
        S2.insert(a[i].s.s);
    }
    int cnt=0;
    for(auto &i:S1)xx[i]=++cnt;
    cnt=0;
    for(auto &i:S2)yy[i]=++cnt;

    for(int ii=1 ; ii<=n ; ii++){
        int k=f(xx[a[ii].s.f],yy[a[ii].s.s])+1;

        for(i=nn+xx[a[ii].s.f]-1 ; i>=1 ; i/=2){
            seg[nn*2*i+1]=max(seg[nn*2*i+1],k);
            lazy[nn*2*i+1]=n*k+yy[a[ii].s.s]-1;
        }
        ans=ans>k?ans:k;
    }

    cout<<ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>m>>n;
    if(m==3)process();
    return 0;
}

Compilation message (stderr)

matrix.cpp: In function 'void process()':
matrix.cpp:74:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j;
           ^

• Subtask 1: 0 / 14
• Subtask 2: 0 / 9
• Subtask 3: 0 / 15
• Subtask 4: 0 / 62