제출 #925162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925162		idiotcomputer	사다리꼴 (balkan11_trapezoid)	C++11	100 / 100	171 ms	60692 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair<ll,ll>
#define f first 
#define s second

#define FOR(i, a,b) for(i = a; i < b; i++)
#define ROF(i, b,a) for(i = b-1; i >= a; i--)

const int mxN = 4*1e5;
int n;

ll mod = 30013;

pii stree[4*mxN+1][2];

pii comp(pii a, pii b){
    if (a.f == b.f){
        return {a.f, (a.s+b.s)%mod};
    } else {
        if (a.f < b.f){
            return b;
        }  
        return a;
    }
}

void upd(int t, pii v, bool w, int l = 0, int r = 4*n-1, int idx = 0){
    if (l > t || r < t){
        return;
    }
    if (l == r){
        stree[idx][w] = v;
        return;
    }
    int m = (l+r)/2;
    upd(t,v,w,l,m,2*idx+1);
    upd(t,v,w,m+1,r,2*idx+2);
    stree[idx][w] = comp(stree[2*idx+1][w],stree[2*idx+2][w]);
    return;
}

pii query(int tl, int tr, bool w, int l = 0, int r = 4*n-1, int idx = 0){
    if (l > tr || r < tl){
        return {0,0};
    }
    
    if (l >= tl && r <= tr){
        return stree[idx][w];
    }
 
    int m = (l+r)/2;
    return comp(query(tl,tr,w,l,m,2*idx+1),query(tl,tr,w,m+1,r,2*idx+2));
}

bool c2(pii &a, pii &b){
    return a.f < b.f;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int i,j;
    FOR (i,0,4*mxN+1){
        stree[i][0] = {0,0};
        stree[i][1] = {0,0};
    }
    
    cin >> n;
    
    vector<pii> p(4*n);
    int vals[n][4];
    FOR(i,0,n){
        cin >> p[4*i].f >> p[4*i+1].f >> p[4*i+2].f >> p[4*i+3].f;
    }
    FOR (i,0,4*n) p[i].s = i;
    sort(p.begin(),p.end(),c2);
    
    int nv = 0;
    int last;
    FOR(i,0,4*n){
        last = p[i].f;
        FOR(j,i,4*n){
            if (p[j].f == last){
                vals[p[j].s/4][p[j].s%4] = nv;
                p[j].f = nv;
            } else {
                break;
            }
        }
        i = j-1;
        nv++;
    }

    pii res[n];
    FOR (i,0,n) res[i] = {1,1};
    
    int cnt[n][2];
    memset(cnt,0,sizeof(cnt));
    
    int idx;
    pii temp;
    FOR (i,0,4*n){
        idx = p[i].s / 4;
        if (cnt[idx][0] == 0 && cnt[idx][1] == 0){
            if (p[i].s%4 < 2){
                temp = query(0,vals[idx][2],1);
                res[idx] = comp(res[idx],{temp.f+1,temp.s});
            } else {
                temp = query(0,vals[idx][0],0);
                res[idx] = comp(res[idx],{temp.f+1,temp.s});   
            }
        }
        
        if (p[i].s%4 < 2){
            cnt[idx][0]++;
            if (cnt[idx][0] == 2){
                upd(vals[idx][3],res[idx],1);
            } 
        } else {
            cnt[idx][1]++;
            if (cnt[idx][1] == 2){
                upd(vals[idx][1],res[idx],0);
            }
        }
    }
    pii tot = {0,0};
    FOR (i,0,n){
        tot = comp(tot, res[i]);
    }
    cout << tot.f << " " << tot.s << '\n';
    return 0;
}

• Subtask 1: 100 / 100