oj.uz

Submission #1022204

# Submission time Handle Problem Language Result Execution time Memory
1022204 2024-07-13T11:00:00 Z dosts Examination (JOI19_examination) C++17
43 / 100
 3000 ms 69708 KB 
//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> vv, int x) {
	return upper_bound(vv.begin(), vv.end(), x) - vv.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[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

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; }
      |           ~~^~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 456 KB Output is correct
7 Correct 12 ms 2420 KB Output is correct
8 Correct 12 ms 2396 KB Output is correct
9 Correct 12 ms 2260 KB Output is correct
10 Correct 9 ms 1368 KB Output is correct
11 Correct 11 ms 1724 KB Output is correct
12 Correct 3 ms 600 KB Output is correct
13 Correct 12 ms 2396 KB Output is correct
14 Correct 12 ms 2380 KB Output is correct
15 Correct 19 ms 2400 KB Output is correct
16 Correct 8 ms 1484 KB Output is correct
17 Correct 5 ms 1312 KB Output is correct
18 Correct 2 ms 724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2678 ms 33696 KB Output is correct
2 Correct 2650 ms 33608 KB Output is correct
3 Correct 2548 ms 33664 KB Output is correct
4 Correct 206 ms 20300 KB Output is correct
5 Correct 2345 ms 21572 KB Output is correct
6 Correct 74 ms 9160 KB Output is correct
7 Correct 2631 ms 32588 KB Output is correct
8 Correct 2161 ms 32840 KB Output is correct
9 Correct 2422 ms 30756 KB Output is correct
10 Correct 1937 ms 19420 KB Output is correct
11 Correct 160 ms 18252 KB Output is correct
12 Correct 89 ms 9160 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2678 ms 33696 KB Output is correct
2 Correct 2650 ms 33608 KB Output is correct
3 Correct 2548 ms 33664 KB Output is correct
4 Correct 206 ms 20300 KB Output is correct
5 Correct 2345 ms 21572 KB Output is correct
6 Correct 74 ms 9160 KB Output is correct
7 Correct 2631 ms 32588 KB Output is correct
8 Correct 2161 ms 32840 KB Output is correct
9 Correct 2422 ms 30756 KB Output is correct
10 Correct 1937 ms 19420 KB Output is correct
11 Correct 160 ms 18252 KB Output is correct
12 Correct 89 ms 9160 KB Output is correct
13 Correct 2686 ms 34100 KB Output is correct
14 Correct 2648 ms 33868 KB Output is correct
15 Correct 2617 ms 33676 KB Output is correct
16 Correct 208 ms 20296 KB Output is correct
17 Correct 1859 ms 21564 KB Output is correct
18 Correct 73 ms 9060 KB Output is correct
19 Correct 2753 ms 34092 KB Output is correct
20 Correct 2653 ms 34096 KB Output is correct
21 Correct 2895 ms 33008 KB Output is correct
22 Correct 2090 ms 19532 KB Output is correct
23 Correct 156 ms 18120 KB Output is correct
24 Correct 50 ms 9160 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 456 KB Output is correct
7 Correct 12 ms 2420 KB Output is correct
8 Correct 12 ms 2396 KB Output is correct
9 Correct 12 ms 2260 KB Output is correct
10 Correct 9 ms 1368 KB Output is correct
11 Correct 11 ms 1724 KB Output is correct
12 Correct 3 ms 600 KB Output is correct
13 Correct 12 ms 2396 KB Output is correct
14 Correct 12 ms 2380 KB Output is correct
15 Correct 19 ms 2400 KB Output is correct
16 Correct 8 ms 1484 KB Output is correct
17 Correct 5 ms 1312 KB Output is correct
18 Correct 2 ms 724 KB Output is correct
19 Correct 2678 ms 33696 KB Output is correct
20 Correct 2650 ms 33608 KB Output is correct
21 Correct 2548 ms 33664 KB Output is correct
22 Correct 206 ms 20300 KB Output is correct
23 Correct 2345 ms 21572 KB Output is correct
24 Correct 74 ms 9160 KB Output is correct
25 Correct 2631 ms 32588 KB Output is correct
26 Correct 2161 ms 32840 KB Output is correct
27 Correct 2422 ms 30756 KB Output is correct
28 Correct 1937 ms 19420 KB Output is correct
29 Correct 160 ms 18252 KB Output is correct
30 Correct 89 ms 9160 KB Output is correct
31 Correct 2686 ms 34100 KB Output is correct
32 Correct 2648 ms 33868 KB Output is correct
33 Correct 2617 ms 33676 KB Output is correct
34 Correct 208 ms 20296 KB Output is correct
35 Correct 1859 ms 21564 KB Output is correct
36 Correct 73 ms 9060 KB Output is correct
37 Correct 2753 ms 34092 KB Output is correct
38 Correct 2653 ms 34096 KB Output is correct
39 Correct 2895 ms 33008 KB Output is correct
40 Correct 2090 ms 19532 KB Output is correct
41 Correct 156 ms 18120 KB Output is correct
42 Correct 50 ms 9160 KB Output is correct
43 Execution timed out 3057 ms 69708 KB Time limit exceeded
44 Halted 0 ms 0 KB -