Submission #1022199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022199		dosts	Examination (JOI19_examination)	C++17	43 / 100	3055 ms	69968 KiB

examination

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
#define all(xx) xx.begin(),xx.end()
#define ps(xxx) cout << (xxx) << endl;
const int N = 3e5+1,inf = 2e9;

struct Query {
    int id,x,y,z;
};


vi v;


int idx(int x) {
    return upper_bound(all(v),x) - v.begin();
}
int ind(vector<int> v, int x) {
	return upper_bound(v.begin(), v.end(), x) - v.begin() - 1;
}
class BIT {
  private:
	int n;  // max x-coordinate
	vector<vector<int>> vals, bit;

  public:
	BIT(int n, vector<pair<int, int>> &todo) : n(n), vals(n + 1), bit(n + 1) {
		// sort points by y-coordinate
		sort(todo.begin(), todo.end(), [](pair<int, int> a, pair<int, int> b) {
			return a.second < b.second;
		});
		// ensures vals and bit are 1-indexed
		for (int i = 1; i <= n; i++) { vals[i].push_back(0); }
		for (auto [x, y] : todo) {
			for (int z = x; z <= n; z += z & -z) {
				if (vals[z].back() != y) { vals[z].push_back(y); }
			}
		}
		for (int i = 1; i <= n; i++) { bit[i].resize(vals[i].size()); }
	}

	/** adds t to the point (x, y) */
	void put(int x, int y, int t = 1) {
		for (; x <= n; x += x & -x) {
			int z = ind(vals[x], y);
			assert(z && vals[x][z] == y);
			for (; z < bit[x].size(); z += z & -z) { bit[x][z] += t; }
		}
	}

	/** @return sum of points in rectangle with top-right corner (x, y) */
	int get(int x, int y) {
		int tot = 0;
		for (; x > 0; x -= x & -x) {
			for (int z = ind(vals[x], y); z > 0; z -= z & -z) {
				tot += bit[x][z];
			}
		}
		return tot;
	}

	/** @returns sum of points with x in [x1, x2] and y in [y1, y2] */
	int get(int x1, int x2, int y1, int y2) {
		if (x1 > x2 || y1 > y2) { return 0; }
		int tr = get(x2, y2);          // top-right
		int tl = get(x1 - 1, y2);      // top-left
		int br = get(x2, y1 - 1);      // bottom-right
		int bl = get(x1 - 1, y1 - 1);  // bottom-left
		return tr - tl - br + bl;
	}
};

void solve() { 
    int n,q;
    cin >> n >> q;
    vi a(n+1),b(n+1);
    for (int i=1;i<=n;i++) cin >> a[i] >> b[i];
    vi inds(n+1);
    iota(inds.begin(),inds.end(),0);
    sort(inds.begin()+1,inds.end(),[&](int x,int y) {
        return a[x]+b[x] < a[y]+b[y];
    });
    vector<Query> queries(q);
    vi ans(q);
    for (int i=0;i<q;i++) {
        cin >> queries[i].x >> queries[i].y >> queries[i].z;
        queries[i].id = i;
    }
    for (int i=1;i<=n;i++) v.push_back(-a[i]),v.push_back(-b[i]);
    for (int i=1;i<=q;i++) v.push_back(-queries[i].x),v.push_back(-queries[i].y);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    sort(queries.begin(), queries.end(),[&](const Query& x,const Query& y) {
        return x.z > y.z;
    });
    int sz = v.size();
    vector<pii> todo;
    for (int i=1;i<=n;i++)  todo.push_back({idx(-a[inds[i]]),idx(-b[inds[i]])});
    for (auto Q : queries) todo.push_back({idx(-Q.x),idx(-Q.y)});
    BIT ft(sz,todo);
    int ptr = n+1;
    for (auto Q : queries) {
        int X = Q.x, Y = Q.y, Z = Q.z,ID = Q.id;
        while (ptr > 1 && a[inds[ptr-1]]+b[inds[ptr-1]] >= Z) {
            --ptr;
            ft.put(idx(-a[inds[ptr]]),idx(-b[inds[ptr]]),1);
        }
        ans[Q.id] = ft.get(idx(-X),idx(-Y));
    }
    for (int i=0;i<q;i++) cout << ans[i] << '\n';
}      
 
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message (stderr)

examination.cpp: In member function 'void BIT::put(int, int, int)':
examination.cpp:54:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for (; z < bit[x].size(); z += z & -z) { bit[x][z] += t; }
      |           ~~^~~~~~~~~~~~~~~
examination.cpp: In function 'void solve()':
examination.cpp:110:39: warning: unused variable 'ID' [-Wunused-variable]
  110 |         int X = Q.x, Y = Q.y, Z = Q.z,ID = Q.id;
      |                                       ^~

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