oj.uz

답안 #467598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467598 2021-08-23T19:20:47 Z Vladth11 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 300 ms 24040 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
 
const ll NMAX = 400001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 30013;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;
 
class AINT{
public:
    pii aint[4 * NMAX];
    pii combine(pii a, pii b){
        if(a.first > b.first)
            return a;
        if(a.first < b.first)
            return b;
        return {a.first, (a.second + b.second) % MOD};
    }
    void update(int node, int st, int dr, int a, pii b){
        if(st == dr){
            aint[node] = b;
            return;
        }
        int mid = (st + dr) / 2;
        if(a <= mid){
            update(node * 2, st, mid, a, b);
        }else{
            update(node * 2 + 1, mid + 1, dr, a, b);
        }
        aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
    }
    pii query(int node, int st, int dr, int a, int b){
        if(a <= st && dr <= b){
            return aint[node];
        }
        int mid = (st + dr) / 2;
        pii rez = {-1, 0};
        if(a <= mid){
            rez = combine(rez, query(node * 2, st, mid, a, b));
        }
        if(b > mid){
            rez = combine(rez, query(node * 2 + 1, mid + 1, dr, a, b));
        }
        return rez;
    }
    void set(int a, pii b){
        update(1, 1, NMAX - 1, a, b);
    }
    pii prefix(int x){
        return query(1, 1, NMAX - 1, 1, x); ///sa evit 0
    }
}st;
 
struct ura{
    int a, b, c, d;
};
 
bool cmp(ura a, ura b){
    return a.a < b.a;
}
 
pii dp[100001];
ura v[100001];
 
vector <int> nrm;
map <int, int> mp;
 
int main() {
  	ios_base::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
    int n, i;
    cin >> n;
    for(i = 1; i <= n; i++){
        cin >> v[i].a >> v[i].b >> v[i].c >> v[i].d;
        nrm.push_back(v[i].a);
        nrm.push_back(v[i].b);
    }
    ///normalizare
    int cnt = 0;
    sort(nrm.begin(), nrm.end());
    for(i = 0; i < nrm.size(); i++){
        if(i == 0 || nrm[i] != nrm[i - 1])
            cnt++;
        mp[nrm[i]] = cnt;
    }   
    nrm.clear();
    for(i = 1; i <= n; i++){
        v[i].a = mp[v[i].a];
        v[i].b = mp[v[i].b];
          nrm.push_back(v[i].c);
        nrm.push_back(v[i].d);
    }
    mp.clear();
    sort(nrm.begin(), nrm.end());
    for(i = 0; i < nrm.size(); i++){
        if(i == 0 || nrm[i] != nrm[i - 1])
            cnt++;
        mp[nrm[i]] = cnt;
    }   
    nrm.clear();
     for(i = 1; i <= n; i++){
        v[i].c = mp[v[i].c];
        v[i].d = mp[v[i].d];
    }
    mp.clear();
    ///gata
    sort(v + 1, v + n + 1, cmp);
    priority_queue <pii> pq;
    pii sol = {0, 0};
    st.set(1, {0, 1});
    for(i = 1; i <= n; i++){
        while(pq.size() && (-pq.top().first) <= v[i].a){
            st.set(v[pq.top().second].d, dp[pq.top().second]);
            pq.pop();
        }
        dp[i] = st.prefix(v[i].c);
        dp[i].first++;
        pq.push({-v[i].b, i});
        sol = st.combine(sol, dp[i]);
    }
    cout << sol.first << " " << sol.second << "\n";
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~
trapezoid.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 8 ms 1028 KB Output is correct
7 Correct 9 ms 1356 KB Output is correct
8 Correct 12 ms 1528 KB Output is correct
9 Correct 24 ms 2752 KB Output is correct
10 Correct 48 ms 5192 KB Output is correct
11 Correct 63 ms 6140 KB Output is correct
12 Correct 140 ms 12428 KB Output is correct
13 Correct 172 ms 14804 KB Output is correct
14 Correct 202 ms 17340 KB Output is correct
15 Correct 228 ms 18536 KB Output is correct
16 Correct 248 ms 19616 KB Output is correct
17 Correct 261 ms 20932 KB Output is correct
18 Correct 241 ms 21872 KB Output is correct
19 Correct 270 ms 21848 KB Output is correct
20 Correct 300 ms 24040 KB Output is correct