oj.uz

답안 #708135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708135 2023-03-11T06:15:09 Z swagchicken 사다리꼴 (balkan11_trapezoid) C++14
0 / 100
 183 ms 9892 KB 
#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 
template <typename T>
void pr(vector<T> &v) {
    FOR(i, 0, sz(v)) cout << v[i] << " ";
    cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
    FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
    cin >> x;
}
template <typename T>
void re(vector<T> &a) {
    FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
    re(first);
    re(rest...);
}
template <typename T>
void pr(T x) {
    cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
    cout << first << " ";
    pr(rest...);
    cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
    cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
 
const ll MOD  = 998244353;
#define inf 1e18;
#define INF INT_MAX

long double PI = 4*atan(1);
long double eps = 1e-12;


template<class T>
class FenwickTree {
    private:
        vector<T> ft;
    public:
        FenwickTree(int m) {
            ft.assign(m + 1, 0);
        }
        
        int LSOne(int x) {
            return x & (-x);
        }

        T RMQ(int j) {
            // this allows array to be 0 indexed while ft is 1 indexed
            j++;
            int maxv = 0;
            for(; j > 0; j -= LSOne(j)) {
                maxv = max(maxv, ft[j]);
            }
            return maxv;
        }
      
        
        void update(int i, T v) {
            i++;
            for(; i < ft.size(); i += LSOne(i)) {
                ft[i] = max(ft[i], v);
            }
        }
};


struct QS {
  int idx, x, y, add;
};

bool cmp(const QS &a, const QS &b) {
  return a.x < b.x;
}

int main() {
    //auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    //ofstream cout("output.txt");
    //ifstream cin("input.txt");
    #ifdef DEBUG
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #endif  

    int n; cin >> n;
    vector<int> botv;
    vector<QS> allq;
    FOR(i,0,n) {
      int a,b,c,d; cin >> a >> b >> c >> d;
      botv.pb(c);
      botv.pb(d);
      allq.pb({i, a, c, 0});
      allq.pb({i, b, d, 1});
    }

    sort(all(botv));

    botv.erase(unique(all(botv)), botv.end());
    for(QS &q : allq) {
      q.y = lower_bound(all(botv), q.y) - botv.begin() + 1;
    }

    sort(all(allq), cmp);
    
    FenwickTree<int> st(210000);

    vector<int> ans(n+5);

    for(QS q : allq) {
      cout << q.x << " " << q.y << " " << q.idx << " " << q.add << endl;
      if(q.add == 0) {
        int val = st.RMQ(q.y);
        ans[q.idx] = val + 1;
      } else {
        st.update(q.y, ans[q.idx]);
      }
    }

    int res = st.RMQ(210000);
    cout << res << " " << -1 << endl;


    //auto stop = chrono::high_resolution_clock::now();
    //auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    //cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}

Compilation message

trapezoid.cpp: In instantiation of 'void FenwickTree<T>::update(int, T) [with T = int]':
trapezoid.cpp:175:34:   required from here
trapezoid.cpp:120:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             for(; i < ft.size(); i += LSOne(i)) {
      |                   ~~^~~~~~~~~~~

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1108 KB Output isn't correct
2 Incorrect 1 ms 1108 KB Output isn't correct
3 Incorrect 1 ms 1108 KB Output isn't correct
4 Incorrect 2 ms 1236 KB Output isn't correct
5 Incorrect 3 ms 1236 KB Output isn't correct
6 Incorrect 5 ms 1460 KB Output isn't correct
7 Incorrect 5 ms 1492 KB Output isn't correct
8 Incorrect 8 ms 1748 KB Output isn't correct
9 Incorrect 20 ms 2024 KB Output isn't correct
10 Incorrect 32 ms 2960 KB Output isn't correct
11 Incorrect 40 ms 3340 KB Output isn't correct
12 Incorrect 91 ms 5656 KB Output isn't correct
13 Incorrect 95 ms 6380 KB Output isn't correct
14 Incorrect 107 ms 7276 KB Output isn't correct
15 Incorrect 135 ms 7692 KB Output isn't correct
16 Incorrect 120 ms 8172 KB Output isn't correct
17 Incorrect 132 ms 8592 KB Output isn't correct
18 Incorrect 183 ms 8968 KB Output isn't correct
19 Incorrect 145 ms 9420 KB Output isn't correct
20 Incorrect 151 ms 9892 KB Output isn't correct