oj.uz

답안 #467518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467518 2021-08-23T12:20:27 Z Vladth11 사다리꼴 (balkan11_trapezoid) C++14
62 / 100
 366 ms 16284 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 = 200001;
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() {
    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; ///daca sortez dupa b, scot logul
    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:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~
trapezoid.cpp:107:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(i = 0; i < nrm.size(); i++){
      |                ~~^~~~~~~~~~~~

Subtask #1
62.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 3 ms 608 KB Output is correct
5 Correct 7 ms 836 KB Output is correct
6 Correct 9 ms 1100 KB Output is correct
7 Correct 12 ms 1280 KB Output is correct
8 Correct 16 ms 1516 KB Output is correct
9 Correct 33 ms 2688 KB Output is correct
10 Correct 68 ms 5188 KB Output is correct
11 Correct 90 ms 6128 KB Output is correct
12 Correct 189 ms 12456 KB Output is correct
13 Incorrect 223 ms 13132 KB Output isn't correct
14 Incorrect 261 ms 14060 KB Output isn't correct
15 Incorrect 296 ms 14468 KB Output isn't correct
16 Incorrect 313 ms 14668 KB Output isn't correct
17 Partially correct 313 ms 15176 KB Partially correct
18 Incorrect 311 ms 15368 KB Output isn't correct
19 Incorrect 326 ms 15824 KB Output isn't correct
20 Incorrect 366 ms 16284 KB Output isn't correct