제출 #140846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
140846		karma	Examination (JOI19_examination)	C++11	43 / 100	3068 ms	780532 KiB

examination

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define FileName      "test"
#define ll            long long
#define ld            long double
#define ull           unsigned long long
#define Debug(x)      cerr << #x << "is " << x << '\n';
#define pb            emplace_back
#define mp            make_pair
#define x             first
#define y             second
//#define LuckyAurora
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using namespace std;
using namespace __gnu_pbds;

template<typename T> inline void Cin(T &x)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}
template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');}
template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);}
template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);}
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

typedef pair<int, int> pii;
const int N = int(1e5) + 7;

struct TSegment
{
    bool Get(int x, int i) {return (x >> i) & 1;}
    struct TTrie {TTrie* chil[2]; int cur;};
    typedef TTrie* PTrie;
    vector<PTrie> t;
    PTrie Node()
    {
          PTrie ptr = new TTrie();
          ptr -> chil[0] = ptr -> chil[1] = NULL, ptr -> cur = 0;
          return ptr;
    }
    void Update(int x, PTrie ptr)
    {
         bool bit; ++ptr -> cur;
         for(int i = 30; i >= 0; --i) {
            bit = Get(x, i);
            if(ptr -> chil[bit] == NULL) ptr -> chil[bit] = Node();
            ptr = ptr -> chil[bit];
            ++ptr -> cur;
         }
    }
    int Count(int x, PTrie ptr)
    {
        int res = ptr -> cur; bool bit;
        for(int i = 30; i >= 0; --i) {
            bit = Get(x, i);
            if(bit && ptr -> chil[0]) res -= ptr -> chil[0] -> cur;
            if(ptr -> chil[bit] == NULL) return res;
            ptr = ptr -> chil[bit];
        }
        return res;
    }
    vector<int> l, h;
    void Build(int x, int low, int high)
    {
        l[x] = low, h[x] = high;
        while(t.size() <= x) t.pb(Node());
        if(l[x] == h[x]) {return;}
        int mid = (low + high) >> 1;
        Build(x << 1, low, mid);
        Build(x << 1 | 1, mid + 1, high);
    }
    void Update(int x, int pos, int val)
    {
        if(l[x] > pos || h[x] < pos) return;
        if(l[x] <= pos && pos <= h[x]) Update(val, t[x]);
        if(l[x] == h[x]) return;
        Update(x << 1, pos, val);
        Update(x << 1 | 1, pos, val);
    }
    int Query(int x, int low, int high, int val)
    {
        if(l[x] > high || h[x] < low) return 0;
        if(l[x] >= low && h[x] <= high) return Count(val, t[x]);
        return Query(x << 1, low, high, val) + Query(x << 1 | 1, low, high, val);
    }
} irene;

int n, Q;
vector<int> v, res;
vector<pii> a;
struct TQuery
{
    int a, b, c, id;
    bool operator <(const TQuery& other)const& {
        return a > other.a;
    }
};
vector<TQuery> q;

void Enter()
{
     Cin(n, Q); q.resize(Q); a.resize(n); res.resize(Q);
     for(pii& p: a) Cin(p.x, p.y), v.pb(p.y);
     sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
     sort(a.begin(), a.end(), [](const pii& a, const pii& b){return a.x > b.x;});
}

void Solve()
{
     for(int i = 0; i < Q; ++i) Cin(q[i].a, q[i].b, q[i].c), q[i].id = i;
     sort(q.begin(), q.end()); irene.l.resize(4 * int(v.size())); irene.h.resize(4 * int(v.size()));
     int j = 0, p; irene.Build(1, 1, int(v.size()));
     for(TQuery que: q) {
         while(a[j].x >= que.a && j < n) {
            p = lower_bound(v.begin(), v.end(), a[j].y) - v.begin() + 1;
            irene.Update(1, p, a[j].x + a[j].y);
            ++j;
         }
         p = lower_bound(v.begin(), v.end(), que.b) - v.begin() + 1;
         res[que.id] = irene.Query(1, p, int(v.size()), que.c);
     }
     for(int i = 0; i < Q; ++i) cout << res[i] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(FileName".inp", "r")) {
        freopen(FileName".inp", "r", stdin);
        freopen(FileName".out", "w", stdout);
    }

    /*int nTest; cin >> nTest;
    while(nTest --)*/ Enter(), Solve();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp:15:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
examination.cpp: In member function 'void TSegment::Build(int, int, int)':
examination.cpp:79:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(t.size() <= x) t.pb(Node());
                        ^
examination.cpp: In function 'int main()':
examination.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(FileName".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(FileName".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 0 / 57