oj.uz

답안 #223071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223071 2020-04-14T15:57:53 Z brcode 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 490 ms 31392 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 12 ms 896 KB Output is correct
6 Correct 14 ms 1280 KB Output is correct
7 Correct 17 ms 1536 KB Output is correct
8 Correct 22 ms 2048 KB Output is correct
9 Correct 41 ms 3572 KB Output is correct
10 Correct 81 ms 6764 KB Output is correct
11 Correct 132 ms 8348 KB Output is correct
12 Correct 228 ms 15968 KB Output is correct
13 Correct 284 ms 18532 KB Output is correct
14 Correct 347 ms 23616 KB Output is correct
15 Correct 367 ms 24656 KB Output is correct
16 Correct 439 ms 26092 KB Output is correct
17 Correct 416 ms 27404 KB Output is correct
18 Correct 389 ms 28764 KB Output is correct
19 Correct 442 ms 29528 KB Output is correct
20 Correct 490 ms 31392 KB Output is correct