oj.uz

Submission #1007679

# Submission time Handle Problem Language Result Execution time Memory
1007679 2024-06-25T10:09:20 Z doducanh trapezoid (balkan11_trapezoid) C++14
45 / 100
 500 ms 18140 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;
void 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;
    }
}
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,make_pair(0,1)){}
    void up(int x,pair<int,int> val){
        for(;x<=n;x+=(x&(-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)))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());
    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++){
        cmax(res,ans[i]);
    }
    cout<<res.fi<<" "<<res.se;
    return 0;
}

Compilation message

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

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 8 ms 4700 KB Output is correct
6 Correct 14 ms 5008 KB Output is correct
7 Correct 25 ms 5140 KB Output is correct
8 Correct 40 ms 5260 KB Output is correct
9 Correct 180 ms 5840 KB Output is correct
10 Execution timed out 897 ms 7240 KB Time limit exceeded
11 Execution timed out 1034 ms 7876 KB Time limit exceeded
12 Execution timed out 1076 ms 10944 KB Time limit exceeded
13 Execution timed out 1039 ms 12316 KB Time limit exceeded
14 Execution timed out 1040 ms 15276 KB Time limit exceeded
15 Execution timed out 1014 ms 16296 KB Time limit exceeded
16 Execution timed out 1066 ms 15532 KB Time limit exceeded
17 Execution timed out 1043 ms 16956 KB Time limit exceeded
18 Execution timed out 1069 ms 18140 KB Time limit exceeded
19 Execution timed out 1066 ms 17908 KB Time limit exceeded
20 Execution timed out 1043 ms 18084 KB Time limit exceeded