oj.uz

Submission #1022199

# Submission time Handle Problem Language Result Execution time Memory
1022199 2024-07-13T10:58:18 Z dosts Examination (JOI19_examination) C++17
43 / 100
 3000 ms 69968 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> 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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 376 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 2352 KB Output is correct
8 Correct 12 ms 2432 KB Output is correct
9 Correct 11 ms 2648 KB Output is correct
10 Correct 6 ms 1372 KB Output is correct
11 Correct 7 ms 1372 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 12 ms 2396 KB Output is correct
14 Correct 11 ms 2404 KB Output is correct
15 Correct 15 ms 2396 KB Output is correct
16 Correct 8 ms 1488 KB Output is correct
17 Correct 5 ms 1368 KB Output is correct
18 Correct 2 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2482 ms 33612 KB Output is correct
2 Correct 2406 ms 33684 KB Output is correct
3 Correct 2563 ms 33608 KB Output is correct
4 Correct 192 ms 20044 KB Output is correct
5 Correct 2311 ms 21512 KB Output is correct
6 Correct 72 ms 9164 KB Output is correct
7 Correct 2757 ms 32708 KB Output is correct
8 Correct 2150 ms 32860 KB Output is correct
9 Correct 2448 ms 30796 KB Output is correct
10 Correct 2187 ms 19444 KB Output is correct
11 Correct 178 ms 18252 KB Output is correct
12 Correct 59 ms 9160 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2482 ms 33612 KB Output is correct
2 Correct 2406 ms 33684 KB Output is correct
3 Correct 2563 ms 33608 KB Output is correct
4 Correct 192 ms 20044 KB Output is correct
5 Correct 2311 ms 21512 KB Output is correct
6 Correct 72 ms 9164 KB Output is correct
7 Correct 2757 ms 32708 KB Output is correct
8 Correct 2150 ms 32860 KB Output is correct
9 Correct 2448 ms 30796 KB Output is correct
10 Correct 2187 ms 19444 KB Output is correct
11 Correct 178 ms 18252 KB Output is correct
12 Correct 59 ms 9160 KB Output is correct
13 Correct 2808 ms 34120 KB Output is correct
14 Correct 2836 ms 34060 KB Output is correct
15 Correct 2794 ms 33508 KB Output is correct
16 Correct 226 ms 20296 KB Output is correct
17 Correct 1992 ms 21732 KB Output is correct
18 Correct 70 ms 9076 KB Output is correct
19 Correct 2904 ms 34100 KB Output is correct
20 Correct 2757 ms 34108 KB Output is correct
21 Correct 2781 ms 33004 KB Output is correct
22 Correct 2196 ms 19528 KB Output is correct
23 Correct 173 ms 18256 KB Output is correct
24 Correct 50 ms 9100 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 376 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 2352 KB Output is correct
8 Correct 12 ms 2432 KB Output is correct
9 Correct 11 ms 2648 KB Output is correct
10 Correct 6 ms 1372 KB Output is correct
11 Correct 7 ms 1372 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 12 ms 2396 KB Output is correct
14 Correct 11 ms 2404 KB Output is correct
15 Correct 15 ms 2396 KB Output is correct
16 Correct 8 ms 1488 KB Output is correct
17 Correct 5 ms 1368 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2482 ms 33612 KB Output is correct
20 Correct 2406 ms 33684 KB Output is correct
21 Correct 2563 ms 33608 KB Output is correct
22 Correct 192 ms 20044 KB Output is correct
23 Correct 2311 ms 21512 KB Output is correct
24 Correct 72 ms 9164 KB Output is correct
25 Correct 2757 ms 32708 KB Output is correct
26 Correct 2150 ms 32860 KB Output is correct
27 Correct 2448 ms 30796 KB Output is correct
28 Correct 2187 ms 19444 KB Output is correct
29 Correct 178 ms 18252 KB Output is correct
30 Correct 59 ms 9160 KB Output is correct
31 Correct 2808 ms 34120 KB Output is correct
32 Correct 2836 ms 34060 KB Output is correct
33 Correct 2794 ms 33508 KB Output is correct
34 Correct 226 ms 20296 KB Output is correct
35 Correct 1992 ms 21732 KB Output is correct
36 Correct 70 ms 9076 KB Output is correct
37 Correct 2904 ms 34100 KB Output is correct
38 Correct 2757 ms 34108 KB Output is correct
39 Correct 2781 ms 33004 KB Output is correct
40 Correct 2196 ms 19528 KB Output is correct
41 Correct 173 ms 18256 KB Output is correct
42 Correct 50 ms 9100 KB Output is correct
43 Execution timed out 3055 ms 69968 KB Time limit exceeded
44 Halted 0 ms 0 KB -