oj.uz

Submission #525408

# Submission time Handle Problem Language Result Execution time Memory
525408 2022-02-11T14:49:19 Z CPSC Examination (JOI19_examination) C++14
100 / 100
 2150 ms 436092 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int> 
using namespace std;
const int N = 5e5 + 5;
int n,q,a[N],b[N],c[N],x[N],y[N],z[N],mx,id,cnt,cur,pas[N];
unordered_map <int, int> shes;
vector <int> tocomp;
unordered_map <int, int> compr[4*N];
vector <int> tree[4*N];
int mxxx[4*N];
vector < pii > vec[4*N],v,v1;
void updatefenw(int node, int idx, int val) {
    for (int i = idx; i <= vec[node].size(); i+=i&(-i)) {
        tree[node][i] += val;
    }
}
int getfenw(int node, int le, int ri) {
    int pas = 0;
    for (int i = ri; i > 0 ; i -= i&(-i)) {
        pas += tree[node][i];
    }
    for (int i = le - 1; i > 0; i-=i&(-i)) {
        pas -= tree[node][i];
    }
    return pas;
}
void update(int node, int le ,int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        vec[node].pb({val,1});
      //  updatefenw(node,val,1);
        return ;
    }
    int mid = (le + ri) / 2;
    update(2 * node, le, mid , idx, val);
    update(2*node + 1, mid + 1, ri, idx, val);
    if (le <= idx && ri >= idx) {
        vec[node].pb({val,1});
        // updatefenw(node,val,1);
    }
}
int getans(int node, int le, int ri, int start, int end, int val1) {
    if (le > end || ri < start) return 0;
    if (le >= start && ri <= end) {
    	int lee = 0;
    	int rii = (int)vec[node].size() - 1;
    	int anss = -1;
    	while (lee <= rii) {
    		int midd = (lee + rii) / 2;
    		if (vec[node][midd].f >= val1) anss = midd, rii = midd - 1;
    		else lee = midd + 1;
		}
		//cout<<node<<" "<<val1<<" "<<anss<<" "<<compr[node][vec[node][anss].f]<<endl;
		if (anss == -1) return 0;
		else
        return getfenw(node,compr[node][vec[node][anss].f],(int)vec[node].size());
    }
    int mid = (le + ri) / 2;
	return getans(2*node, le, mid,start,end,val1) + getans(2*node + 1, mid + 1, ri, start,end,val1);
}
void add(int idx) {
    id = v[idx].s;
    update(1,1,mx,a[id],b[id]);
}
void update1(int node, int le ,int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        //cout<<node<<" "<<compr[node][val]<<endl;
        updatefenw(node,compr[node][val],1);
        return ;
    }
    int mid = (le + ri) / 2;
    update1(2 * node, le, mid , idx, val);
    update1(2*node + 1, mid + 1, ri, idx, val);
    if (le <= idx && ri >= idx) {
        // cout<<node<<" "<<compr[node][val]<<endl;
        updatefenw(node,compr[node][val],1);
    }
}
void add1(int idx) {
	id = v[idx].s;
	update1(1,1,mx,a[id],b[id]);
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for (int i = 1; i <= n; i++) {
        cin>>a[i]>>b[i];
        tocomp.pb(a[i]);tocomp.pb(b[i]);
        v.pb({a[i] + b[i],i});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    for (int i = 1; i <= q; i++) {
        cin>>x[i]>>y[i]>>z[i];
        tocomp.pb(x[i]);
        tocomp.pb(y[i]);
        v1.pb({z[i],i});
    }
    sort(tocomp.begin(),tocomp.end());
    cnt = 1;
    shes[tocomp[0]] = 1;
    mx = 1;
    for (int i = 1; i < tocomp.size(); i++) {
        if (tocomp[i] != tocomp[i - 1]) cnt++;
        mx = cnt;
        shes[tocomp[i]] = cnt;
    }
    for (int i = 1; i <= n; i++) {
        a[i] = shes[a[i]];
        b[i] = shes[b[i]];
    }for (int i = 1; i <= q; i++) {
        x[i] = shes[x[i]]; y[i] = shes[y[i]];
    }
    sort(v1.begin(),v1.end());
    reverse(v1.begin(),v1.end());
    cur = 0;
    for(int i = 0; i < v1.size(); i++) {
        while (cur < v.size() && v[cur].f >= v1[i].f) {
            add(cur);
            cur++;
        }
        //pas[v1[i].s] = getans(1,1,mx,x[v1[i].s],mx,y[v1[i].s]);
    }
    for (int i = 1; i <= 4 * mx; i++) {
    	sort(vec[i].begin(),vec[i].end());
    	int cnt = 0;
    	for (int j = 0; j < vec[i].size(); j++) {
    	    
    		if (j == 0) cnt++;
    		else if (vec[i][j].f != vec[i][j - 1].f) cnt++;
   			compr[i][vec[i][j].f] = cnt ;
   			//cout<<i<<" "<<vec[i][j].f<<" "<<cnt<<endl;
		}
		mxxx[i] = cnt;
		tree[i] = vector <int> (vec[i].size() + 2,0);
	}
    cur = 0;
    for(int i = 0; i < v1.size(); i++) {
        while (cur < v.size() && v[cur].f >= v1[i].f) {
            add1(cur);
            cur++;
        }
        pas[v1[i].s] = getans(1,1,mx,x[v1[i].s],mx,y[v1[i].s]);
        //cout<<endl;
    }
    for (int i = 1; i <= q; i++) cout<<pas[i]<<" ";
}

Compilation message

examination.cpp: In function 'void updatefenw(int, int, int)':
examination.cpp:16:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = idx; i <= vec[node].size(); i+=i&(-i)) {
      |                       ~~^~~~~~~~~~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main() {
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 1; i < tocomp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
examination.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i = 0; i < v1.size(); i++) {
      |                    ~~^~~~~~~~~~~
examination.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         while (cur < v.size() && v[cur].f >= v1[i].f) {
      |                ~~~~^~~~~~~~~~
examination.cpp:131:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |      for (int j = 0; j < vec[i].size(); j++) {
      |                      ~~^~~~~~~~~~~~~~~
examination.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i = 0; i < v1.size(); i++) {
      |                    ~~^~~~~~~~~~~
examination.cpp:143:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         while (cur < v.size() && v[cur].f >= v1[i].f) {
      |                ~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 203772 KB Output is correct
2 Correct 101 ms 203880 KB Output is correct
3 Correct 103 ms 203868 KB Output is correct
4 Correct 105 ms 203884 KB Output is correct
5 Correct 114 ms 203864 KB Output is correct
6 Correct 99 ms 203820 KB Output is correct
7 Correct 128 ms 209860 KB Output is correct
8 Correct 126 ms 209744 KB Output is correct
9 Correct 135 ms 209948 KB Output is correct
10 Correct 136 ms 207264 KB Output is correct
11 Correct 113 ms 207624 KB Output is correct
12 Correct 127 ms 204164 KB Output is correct
13 Correct 131 ms 209956 KB Output is correct
14 Correct 126 ms 209844 KB Output is correct
15 Correct 127 ms 209796 KB Output is correct
16 Correct 116 ms 207580 KB Output is correct
17 Correct 130 ms 206932 KB Output is correct
18 Correct 113 ms 204100 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1604 ms 336676 KB Output is correct
2 Correct 1651 ms 339176 KB Output is correct
3 Correct 1572 ms 339372 KB Output is correct
4 Correct 662 ms 283188 KB Output is correct
5 Correct 687 ms 301208 KB Output is correct
6 Correct 232 ms 217340 KB Output is correct
7 Correct 1491 ms 338280 KB Output is correct
8 Correct 1542 ms 338328 KB Output is correct
9 Correct 1355 ms 335776 KB Output is correct
10 Correct 591 ms 298180 KB Output is correct
11 Correct 542 ms 273364 KB Output is correct
12 Correct 179 ms 214876 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1604 ms 336676 KB Output is correct
2 Correct 1651 ms 339176 KB Output is correct
3 Correct 1572 ms 339372 KB Output is correct
4 Correct 662 ms 283188 KB Output is correct
5 Correct 687 ms 301208 KB Output is correct
6 Correct 232 ms 217340 KB Output is correct
7 Correct 1491 ms 338280 KB Output is correct
8 Correct 1542 ms 338328 KB Output is correct
9 Correct 1355 ms 335776 KB Output is correct
10 Correct 591 ms 298180 KB Output is correct
11 Correct 542 ms 273364 KB Output is correct
12 Correct 179 ms 214876 KB Output is correct
13 Correct 1726 ms 339784 KB Output is correct
14 Correct 1651 ms 339652 KB Output is correct
15 Correct 1588 ms 339148 KB Output is correct
16 Correct 700 ms 283516 KB Output is correct
17 Correct 786 ms 301636 KB Output is correct
18 Correct 233 ms 217204 KB Output is correct
19 Correct 1748 ms 339708 KB Output is correct
20 Correct 1641 ms 339620 KB Output is correct
21 Correct 1601 ms 338020 KB Output is correct
22 Correct 590 ms 298376 KB Output is correct
23 Correct 495 ms 273400 KB Output is correct
24 Correct 180 ms 215076 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 203772 KB Output is correct
2 Correct 101 ms 203880 KB Output is correct
3 Correct 103 ms 203868 KB Output is correct
4 Correct 105 ms 203884 KB Output is correct
5 Correct 114 ms 203864 KB Output is correct
6 Correct 99 ms 203820 KB Output is correct
7 Correct 128 ms 209860 KB Output is correct
8 Correct 126 ms 209744 KB Output is correct
9 Correct 135 ms 209948 KB Output is correct
10 Correct 136 ms 207264 KB Output is correct
11 Correct 113 ms 207624 KB Output is correct
12 Correct 127 ms 204164 KB Output is correct
13 Correct 131 ms 209956 KB Output is correct
14 Correct 126 ms 209844 KB Output is correct
15 Correct 127 ms 209796 KB Output is correct
16 Correct 116 ms 207580 KB Output is correct
17 Correct 130 ms 206932 KB Output is correct
18 Correct 113 ms 204100 KB Output is correct
19 Correct 1604 ms 336676 KB Output is correct
20 Correct 1651 ms 339176 KB Output is correct
21 Correct 1572 ms 339372 KB Output is correct
22 Correct 662 ms 283188 KB Output is correct
23 Correct 687 ms 301208 KB Output is correct
24 Correct 232 ms 217340 KB Output is correct
25 Correct 1491 ms 338280 KB Output is correct
26 Correct 1542 ms 338328 KB Output is correct
27 Correct 1355 ms 335776 KB Output is correct
28 Correct 591 ms 298180 KB Output is correct
29 Correct 542 ms 273364 KB Output is correct
30 Correct 179 ms 214876 KB Output is correct
31 Correct 1726 ms 339784 KB Output is correct
32 Correct 1651 ms 339652 KB Output is correct
33 Correct 1588 ms 339148 KB Output is correct
34 Correct 700 ms 283516 KB Output is correct
35 Correct 786 ms 301636 KB Output is correct
36 Correct 233 ms 217204 KB Output is correct
37 Correct 1748 ms 339708 KB Output is correct
38 Correct 1641 ms 339620 KB Output is correct
39 Correct 1601 ms 338020 KB Output is correct
40 Correct 590 ms 298376 KB Output is correct
41 Correct 495 ms 273400 KB Output is correct
42 Correct 180 ms 215076 KB Output is correct
43 Correct 2150 ms 435956 KB Output is correct
44 Correct 2115 ms 435904 KB Output is correct
45 Correct 2095 ms 436092 KB Output is correct
46 Correct 840 ms 327252 KB Output is correct
47 Correct 1024 ms 358388 KB Output is correct
48 Correct 241 ms 217048 KB Output is correct
49 Correct 1997 ms 434036 KB Output is correct
50 Correct 2049 ms 434080 KB Output is correct
51 Correct 1866 ms 430076 KB Output is correct
52 Correct 890 ms 359868 KB Output is correct
53 Correct 678 ms 316712 KB Output is correct