Submission #594871

#	Time	Username	Problem	Language	Result	Execution time	Memory
594871		Do_you_copy	Examination (JOI19_examination)	C++17	100 / 100	456 ms	25776 KiB

examination

#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;

int n, qq;

struct bit2d{
    vector <int> nodex;
    vector <vector <int>> node, val;
    void pre_build(){
        sort(nodex.begin(), nodex.end());
        nodex.resize(unique(nodex.begin(), nodex.end()) - nodex.begin());
        node.resize(nodex.size() + 1);
        val.resize(nodex.size() + 1);
    }
    void fake_update(int xx, int yy){
        int x = upper_bound(nodex.begin(), nodex.end(), xx) - nodex.begin();
        for (; x < node.size(); x += x & -x){
            node[x].pb(yy);
        }
    }
    void build(){
        for (int i = 1; i < node.size(); ++i){
            sort(node[i].begin(), node[i].end());
            node[i].resize(unique(node[i].begin(), node[i].end()) - node[i].begin());
            val[i].resize(node[i].size() + 1);
        }
    }
    void update(int xx, int yy){
        int x = upper_bound(nodex.begin(), nodex.end(), xx) - nodex.begin();
        for (; x < node.size(); x += x & -x){
            int y = upper_bound(node[x].begin(), node[x].end(), yy) - node[x].begin();
            for (int j = y; j < val[x].size(); j += j & -j){
                ++val[x][j];
            }
        }
    }
    int get(int xx, int yy){
        int sum = 0;
        int x = upper_bound(nodex.begin(), nodex.end(), xx) - nodex.begin();
        for (; x; x -= x & -x){
            int y = upper_bound(node[x].begin(), node[x].end(), yy) - node[x].begin();
            for (int j = y; j; j -= j & -j){
                sum += val[x][j];
            }
        }
        return sum;
    }
}bit;

struct TPoint{
    int x, y, z;
};
TPoint a[maxN];

struct TQuery{
    int A, B, C, idx;
};
TQuery q[maxN];

int ans[maxN];

void Init(){
    cin >> n >> qq;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].x >> a[i].y;
        a[i].z = a[i].x + a[i].y;
        bit.nodex.pb(-a[i].x);
    }
    bit.pre_build();
    sort(a + 1, a + n + 1,[](const auto &i, const auto &j){
        return i.z > j.z;
    });
    for (int i = 1; i <= n; ++i){
        bit.fake_update(-a[i].x, -a[i].y);
    }
    bit.build();
    for (int i = 1; i <= qq; ++i){
        cin >> q[i].A >> q[i].B >> q[i].C;
        q[i].idx = i;
    }
    sort(q + 1, q + qq + 1,[](const auto &i, const auto &j){
        return i.C > j.C;
    });
    int j = 1;
    for (int i = 1; i <= qq; ++i){
        while (j <= n && a[j].z >= q[i].C){
            //cerr << a[j].x << " " << a[j].y << "?\n";
            bit.update(-a[j].x, -a[j].y);
            ++j;
        }
        //cerr << q[i].A << " " << q[i].B << "\n";
        ans[q[i].idx] = bit.get(-q[i].A, -q[i].B);
    }
    for (int i = 1; i <= qq; ++i) cout << ans[i] << "\n";
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message (stderr)

examination.cpp: In member function 'void bit2d::fake_update(int, int)':
examination.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (; x < node.size(); x += x & -x){
      |                ~~^~~~~~~~~~~~~
examination.cpp: In member function 'void bit2d::build()':
examination.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int i = 1; i < node.size(); ++i){
      |                         ~~^~~~~~~~~~~~~
examination.cpp: In member function 'void bit2d::update(int, int)':
examination.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (; x < node.size(); x += x & -x){
      |                ~~^~~~~~~~~~~~~
examination.cpp:57:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for (int j = y; j < val[x].size(); j += j & -j){
      |                             ~~^~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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