oj.uz

Submission #1007656

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

using namespace std;
#define fi first
#define se second
const int maxn=1e5+7;
const int mod=30013;
const int maxx=1e9+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
{
private:
    int n;
    vector<pair<int,int>>t;
public:
    BIT(){}
    BIT(int n):n(n),t(n,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;
    }
};
vector<int>a,b,c,d;
int n;
pair<int,int>ans[maxn];
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    a.resize(n+1);b.resize(n+1);
    c.resize(n+1);d.resize(n+1);
    vector<pair<int,int>>top;
    vector<pair<int,int>>bot;
    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]){
            pair<int,int>tmp=t.get(id(c[i],bot)-1);
            ans[i]={tmp.fi+1,tmp.se};
        }
        else if(x==b[i]){
            t.up(id(d[i],bot),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:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main()
      | ^~~~

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 560 KB Output is correct
5 Correct 10 ms 600 KB Output is correct
6 Correct 20 ms 604 KB Output is correct
7 Correct 38 ms 604 KB Output is correct
8 Correct 52 ms 936 KB Output is correct
9 Correct 208 ms 1328 KB Output is correct
10 Execution timed out 786 ms 2252 KB Time limit exceeded
11 Execution timed out 1044 ms 2704 KB Time limit exceeded
12 Execution timed out 1055 ms 4540 KB Time limit exceeded
13 Execution timed out 1032 ms 5392 KB Time limit exceeded
14 Execution timed out 1039 ms 6068 KB Time limit exceeded
15 Execution timed out 1059 ms 6436 KB Time limit exceeded
16 Execution timed out 1046 ms 6836 KB Time limit exceeded
17 Execution timed out 1020 ms 7352 KB Time limit exceeded
18 Execution timed out 1031 ms 7732 KB Time limit exceeded
19 Execution timed out 1070 ms 8120 KB Time limit exceeded
20 Execution timed out 1071 ms 8376 KB Time limit exceeded