oj.uz

Submission #525405

# Submission time Handle Problem Language Result Execution time Memory
525405 2022-02-11T14:45:09 Z CPSC Examination (JOI19_examination) C++14
2 / 100
 3000 ms 443380 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;
map <int, int> compr[4*N];
unordered_map <int, int> tree[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;
		}
	}
    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:15: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]
   15 |     for (int i = idx; i <= vec[node].size(); i+=i&(-i)) {
      |                       ~~^~~~~~~~~~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:86:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 | main() {
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 1; i < tocomp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
examination.cpp:120: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]
  120 |     for(int i = 0; i < v1.size(); i++) {
      |                    ~~^~~~~~~~~~~
examination.cpp:121: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]
  121 |         while (cur < v.size() && v[cur].f >= v1[i].f) {
      |                ~~~~^~~~~~~~~~
examination.cpp:130: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]
  130 |      for (int j = 0; j < vec[i].size(); j++) {
      |                      ~~^~~~~~~~~~~~~~~
examination.cpp:139: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]
  139 |     for(int i = 0; i < v1.size(); i++) {
      |                    ~~^~~~~~~~~~~
examination.cpp:140: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]
  140 |         while (cur < v.size() && v[cur].f >= v1[i].f) {
      |                ~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 250824 KB Output is correct
2 Correct 117 ms 250728 KB Output is correct
3 Correct 117 ms 250816 KB Output is correct
4 Correct 122 ms 250860 KB Output is correct
5 Correct 118 ms 250792 KB Output is correct
6 Correct 117 ms 250772 KB Output is correct
7 Correct 153 ms 256964 KB Output is correct
8 Correct 154 ms 256980 KB Output is correct
9 Correct 160 ms 257080 KB Output is correct
10 Correct 136 ms 254148 KB Output is correct
11 Correct 141 ms 255436 KB Output is correct
12 Correct 132 ms 251144 KB Output is correct
13 Correct 154 ms 257272 KB Output is correct
14 Correct 147 ms 257192 KB Output is correct
15 Correct 150 ms 257196 KB Output is correct
16 Correct 151 ms 255576 KB Output is correct
17 Correct 132 ms 253700 KB Output is correct
18 Correct 121 ms 251136 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3092 ms 443380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3092 ms 443380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 250824 KB Output is correct
2 Correct 117 ms 250728 KB Output is correct
3 Correct 117 ms 250816 KB Output is correct
4 Correct 122 ms 250860 KB Output is correct
5 Correct 118 ms 250792 KB Output is correct
6 Correct 117 ms 250772 KB Output is correct
7 Correct 153 ms 256964 KB Output is correct
8 Correct 154 ms 256980 KB Output is correct
9 Correct 160 ms 257080 KB Output is correct
10 Correct 136 ms 254148 KB Output is correct
11 Correct 141 ms 255436 KB Output is correct
12 Correct 132 ms 251144 KB Output is correct
13 Correct 154 ms 257272 KB Output is correct
14 Correct 147 ms 257192 KB Output is correct
15 Correct 150 ms 257196 KB Output is correct
16 Correct 151 ms 255576 KB Output is correct
17 Correct 132 ms 253700 KB Output is correct
18 Correct 121 ms 251136 KB Output is correct
19 Execution timed out 3092 ms 443380 KB Time limit exceeded
20 Halted 0 ms 0 KB -