oj.uz

Submission #1022217

# Submission time Handle Problem Language Result Execution time Memory
1022217 2024-07-13T11:11:59 Z dosts Examination (JOI19_examination) C++17
43 / 100
 3000 ms 62040 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]])});
    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 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 9 ms 2248 KB Output is correct
8 Correct 13 ms 2140 KB Output is correct
9 Correct 14 ms 2140 KB Output is correct
10 Correct 5 ms 1232 KB Output is correct
11 Correct 6 ms 1492 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 14 ms 2036 KB Output is correct
14 Correct 11 ms 2140 KB Output is correct
15 Correct 14 ms 2224 KB Output is correct
16 Correct 5 ms 1372 KB Output is correct
17 Correct 6 ms 1372 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 1556 ms 26168 KB Output is correct
2 Correct 1523 ms 26320 KB Output is correct
3 Correct 1539 ms 26164 KB Output is correct
4 Correct 213 ms 18384 KB Output is correct
5 Correct 1236 ms 19508 KB Output is correct
6 Correct 61 ms 8392 KB Output is correct
7 Correct 1917 ms 26056 KB Output is correct
8 Correct 1612 ms 25956 KB Output is correct
9 Correct 1968 ms 25208 KB Output is correct
10 Correct 1190 ms 18160 KB Output is correct
11 Correct 134 ms 17352 KB Output is correct
12 Correct 44 ms 8136 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1556 ms 26168 KB Output is correct
2 Correct 1523 ms 26320 KB Output is correct
3 Correct 1539 ms 26164 KB Output is correct
4 Correct 213 ms 18384 KB Output is correct
5 Correct 1236 ms 19508 KB Output is correct
6 Correct 61 ms 8392 KB Output is correct
7 Correct 1917 ms 26056 KB Output is correct
8 Correct 1612 ms 25956 KB Output is correct
9 Correct 1968 ms 25208 KB Output is correct
10 Correct 1190 ms 18160 KB Output is correct
11 Correct 134 ms 17352 KB Output is correct
12 Correct 44 ms 8136 KB Output is correct
13 Correct 1567 ms 26588 KB Output is correct
14 Correct 1563 ms 26312 KB Output is correct
15 Correct 1565 ms 26116 KB Output is correct
16 Correct 188 ms 18896 KB Output is correct
17 Correct 1048 ms 19656 KB Output is correct
18 Correct 75 ms 8660 KB Output is correct
19 Correct 1531 ms 26584 KB Output is correct
20 Correct 1607 ms 26440 KB Output is correct
21 Correct 1971 ms 26060 KB Output is correct
22 Correct 1244 ms 18292 KB Output is correct
23 Correct 135 ms 17516 KB Output is correct
24 Correct 44 ms 8392 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 9 ms 2248 KB Output is correct
8 Correct 13 ms 2140 KB Output is correct
9 Correct 14 ms 2140 KB Output is correct
10 Correct 5 ms 1232 KB Output is correct
11 Correct 6 ms 1492 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 14 ms 2036 KB Output is correct
14 Correct 11 ms 2140 KB Output is correct
15 Correct 14 ms 2224 KB Output is correct
16 Correct 5 ms 1372 KB Output is correct
17 Correct 6 ms 1372 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 1556 ms 26168 KB Output is correct
20 Correct 1523 ms 26320 KB Output is correct
21 Correct 1539 ms 26164 KB Output is correct
22 Correct 213 ms 18384 KB Output is correct
23 Correct 1236 ms 19508 KB Output is correct
24 Correct 61 ms 8392 KB Output is correct
25 Correct 1917 ms 26056 KB Output is correct
26 Correct 1612 ms 25956 KB Output is correct
27 Correct 1968 ms 25208 KB Output is correct
28 Correct 1190 ms 18160 KB Output is correct
29 Correct 134 ms 17352 KB Output is correct
30 Correct 44 ms 8136 KB Output is correct
31 Correct 1567 ms 26588 KB Output is correct
32 Correct 1563 ms 26312 KB Output is correct
33 Correct 1565 ms 26116 KB Output is correct
34 Correct 188 ms 18896 KB Output is correct
35 Correct 1048 ms 19656 KB Output is correct
36 Correct 75 ms 8660 KB Output is correct
37 Correct 1531 ms 26584 KB Output is correct
38 Correct 1607 ms 26440 KB Output is correct
39 Correct 1971 ms 26060 KB Output is correct
40 Correct 1244 ms 18292 KB Output is correct
41 Correct 135 ms 17516 KB Output is correct
42 Correct 44 ms 8392 KB Output is correct
43 Correct 2320 ms 61964 KB Output is correct
44 Correct 2344 ms 62040 KB Output is correct
45 Correct 2274 ms 61776 KB Output is correct
46 Correct 259 ms 32460 KB Output is correct
47 Correct 1813 ms 33960 KB Output is correct
48 Correct 62 ms 8396 KB Output is correct
49 Execution timed out 3059 ms 61748 KB Time limit exceeded
50 Halted 0 ms 0 KB -