Submission #223071

#	Time	Username	Problem	Language	Result	Execution time	Memory
223071		brcode	trapezoid (balkan11_trapezoid)	C++14	100 / 100	490 ms	31392 KiB

trapezoid

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const long long MAXN = 5e5+5;
const int MOD = 30013;
pair<int,int> seg[4*MAXN];
int dp[MAXN];
int dp2[MAXN];
int a[MAXN];
int b[MAXN];
int c[MAXN];
int d[MAXN];
map<int,int> up;
map<int,int> down;
vector<pair<int,int>> v1;
vector<pair<int,int>> v2;
pair<int,int> query(int curr,int l,int r,int tl,int tr){
    if(l>tr||r<tl){
        return make_pair(0,0);
    }
    if(tl<=l && r<=tr){
        return seg[curr];
    }
    int mid = (l+r)/2;
    auto f = query(2*curr,l,mid,tl,tr);
    auto s = query(2*curr+1,mid+1,r,tl,tr);
    pair<int,int> ans= make_pair(0,0);
    if(f.first == s.first){
        ans.first = f.first;
        ans.second = f.second+s.second;
        ans.second%=MOD;
    }else if(f.first>s.first){
        ans = f;
    }else{
        ans = s;
    }
    return ans;
}
void update(int curr,int l,int r,int ind,pair<int,int> val){
    //cout<<l<<" "<<r<<endl;
    if(l==r){
        seg[curr] = val;
        return;
    }
    int mid = (l+r)/2;
    if(ind<=mid){
        update(2*curr,l,mid,ind,val);
    }else{
        update(2*curr+1,mid+1,r,ind,val);
    }
    if(seg[2*curr].first == seg[2*curr+1].first){
        seg[curr].first = seg[2*curr].first;
        seg[curr].second = seg[2*curr].second + seg[2*curr+1].second;
        seg[curr].second%=MOD;
    }else if(seg[2*curr].first>seg[2*curr+1].first){
        seg[curr] = seg[2*curr];
    }else{
        seg[curr] = seg[2*curr+1];
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cin>>b[i];
        cin>>c[i];
        cin>>d[i];
        v1.push_back(make_pair(a[i],i));
        v1.push_back(make_pair(b[i],i));
        v2.push_back(make_pair(c[i],i));
        v2.push_back(make_pair(d[i],i));
       
    }
    sort(v2.begin(),v2.end());
    sort(v1.begin(),v1.end());
    for(int i=0;i<2*n;i++){
        up[v1[i].first] = i+1;
        down[v2[i].first] = i+1;
        
    }
    for(int i=1;i<=n;i++){
        a[i] = up[a[i]];
        b[i] = up[b[i]];
        c[i] = down[c[i]];
        d[i] = down[d[i]];
        
    }
    for(int i=0;i<2*n;i++){
        int curr = v2[i].second;
       
        if(dp[curr] == 0){
            auto hold = query(1,1,2*n,1,a[curr]-1);
            
            if(hold.first == 0){
                hold.second = 1;
            }
            dp[curr] = hold.first+1;
            dp2[curr] = hold.second;
        }else{
            
            update(1,1,2*n,b[curr],make_pair(dp[curr],dp2[curr]));
            
        }
    }
    int res1 = 0;
    int res2 = 0;
    for(int i=1;i<=n;i++){
        res1 = max(res1,dp[i]);
    }
    for(int i=1;i<=n;i++){
        if(dp[i] == res1){
            res2+=dp2[i];
            res2%=MOD;
        }
    }
    cout<<res1<<" "<<res2<<endl;
    
}

• Subtask 1: 100 / 100