oj.uz

Submission #1007683

# Submission time Handle Problem Language Result Execution time Memory
1007683 2024-06-25T10:14:36 Z doducanh trapezoid (balkan11_trapezoid) C++14
45 / 100
 500 ms 18600 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define fi first
#define se second
const int maxn=1e5+7;
const int mod=30013;
const int maxx=1e15+7;
pair<int,int> cmax(pair<int,int>a,pair<int,int>b)
{
    if(a.fi<b.fi)a=b;
    else{
        if(a.fi==b.fi&&a.fi!=0)a.se=(a.se+b.se)%mod;
    }
    return a;
}
int id(int x,vector<pair<int,int>>tmp)
{
    return lower_bound(tmp.begin(),tmp.end(),make_pair(x,-maxx))-tmp.begin()+1;
}
struct BIT
{
    int n;
    vector<pair<int,int>>t;
    BIT(){}
    BIT(int n):n(n),t(n+7){}
    void up(int x,pair<int,int> val){
        for(;x<n;x+=(x&(-x)))t[x]=cmax(t[x],val);
    }
    pair<int,int>get(int x)
    {
        if(x<=0)return {0,1};
        pair<int,int>res={0,1};
        for(;x;x-=(x&(-x)))res=cmax(res,t[x]);
        return res;
    }
};
int a[maxn],b[maxn],c[maxn],d[maxn];
int n;
pair<int,int>ans[maxn];
vector<pair<int,int>>top;
vector<pair<int,int>>bot;
main()
{
//    freopen("trapezoid.in","r",stdin);
//    freopen("trapezoid.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        top.push_back({a[i],i});
        top.push_back({b[i],i});
        bot.push_back({c[i],i});
        bot.push_back({d[i],i});
    }
    sort(top.begin(),top.end());
    sort(bot.begin(),bot.end());
    BIT t(bot.size()+7);
    for(pair<int,int>p:top){
        int x=p.fi;
        int i=p.se;
        if(x==a[i]){
            int x=id(c[i],bot)-1;
            pair<int,int>tmp=t.get(x);
            ans[i]={tmp.fi+1,tmp.se};
        }
        else if(x==b[i]){
            int x=id(d[i],bot);
            t.up(x,ans[i]);
        }
    }
    pair<int,int>res={0,0};
    for(int i=1;i<=n;i++){
        res=cmax(res,ans[i]);
    }
    cout<<res.fi<<" "<<res.se;
    return 0;
}

Compilation message

trapezoid.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main()
      | ^~~~

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 4568 KB Output is correct
5 Correct 10 ms 4696 KB Output is correct
6 Correct 20 ms 5016 KB Output is correct
7 Correct 47 ms 5096 KB Output is correct
8 Correct 55 ms 5176 KB Output is correct
9 Correct 229 ms 5856 KB Output is correct
10 Execution timed out 991 ms 7108 KB Time limit exceeded
11 Execution timed out 1081 ms 7968 KB Time limit exceeded
12 Execution timed out 1036 ms 10932 KB Time limit exceeded
13 Execution timed out 1047 ms 12220 KB Time limit exceeded
14 Execution timed out 1064 ms 15276 KB Time limit exceeded
15 Execution timed out 1068 ms 16292 KB Time limit exceeded
16 Execution timed out 1062 ms 15412 KB Time limit exceeded
17 Execution timed out 1053 ms 16804 KB Time limit exceeded
18 Execution timed out 1061 ms 17272 KB Time limit exceeded
19 Execution timed out 1065 ms 16956 KB Time limit exceeded
20 Execution timed out 1034 ms 18600 KB Time limit exceeded