Submission #223071

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
223071	2020-04-14T15:57:53 Z	brcode	trapezoid (balkan11_trapezoid)	C++14	100 / 100	490 ms	31392 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	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