Submission #249883

#	Time	Username	Problem	Language	Result	Execution time	Memory
249883		Mercenary	trapezoid (balkan11_trapezoid)	C++14	100 / 100	99 ms	6644 KiB

trapezoid

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 5;
const int logn = log2(maxn) + 1;
const int mod = 30013;
void add(int & x , int y){
    x += y;
    if(x >= mod)x -= mod;
}
struct node{
    int a , b , c , d;
    bool operator < (const node other){
        return a < other.a;
    }
}a[maxn];
ii operator + (const ii a , const ii b){
    if(a.first != b.first)return max(a,b);
    return mp(a.first, (a.second + b.second) % mod);
}

int n;
ii s[maxn * 4];

void update(int x , ii val){
    for( ; x <= n ; x += x & -x){
        s[x] = s[x] + val;
    }
}

ii query(int x){
    ii res = mp(0,0);
    for( ; x > 0 ; x &= x - 1)res = res + s[x];
    return res;
}
ii dp[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    vector<int> val;
    cin >> n;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
        val.pb(a[i].d);
    }
    sort(val.begin(),val.end());
    priority_queue<ii,vector<ii>,greater<ii>> pq;
    sort(a + 1 , a + n + 1);
    ii res = mp(0,1);
    for(int i = 1 ; i <= n ; ++i){
        while(pq.size() && pq.top().first < a[i].a){
            update(lower_bound(val.begin(),val.end(),a[pq.top().second].d)-val.begin()+1,dp[pq.top().second]);
            pq.pop();
        }
        dp[i] = query(lower_bound(val.begin(),val.end(),a[i].c) - val.begin());
        if(dp[i].first == 0)dp[i] = mp(0 , 1);
        dp[i].first++;
        res = res + dp[i];
        pq.push(mp(a[i].b , i));
    }
    cout << res.first << " " << res.second << endl;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:56:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100