oj.uz

답안 #525404

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525404 2022-02-11T14:44:12 Z CPSC Examination (JOI19_examination) C++14
0 / 100
 3000 ms 537280 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 <= mx; 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: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
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 250852 KB Output is correct
2 Correct 123 ms 250840 KB Output is correct
3 Correct 120 ms 250904 KB Output is correct
4 Correct 120 ms 250820 KB Output is correct
5 Correct 119 ms 250768 KB Output is correct
6 Correct 118 ms 250872 KB Output is correct
7 Correct 176 ms 262808 KB Output is correct
8 Correct 180 ms 262752 KB Output is correct
9 Correct 173 ms 262664 KB Output is correct
10 Correct 154 ms 257476 KB Output is correct
11 Correct 144 ms 255604 KB Output is correct
12 Incorrect 125 ms 251184 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3119 ms 537280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3119 ms 537280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 250852 KB Output is correct
2 Correct 123 ms 250840 KB Output is correct
3 Correct 120 ms 250904 KB Output is correct
4 Correct 120 ms 250820 KB Output is correct
5 Correct 119 ms 250768 KB Output is correct
6 Correct 118 ms 250872 KB Output is correct
7 Correct 176 ms 262808 KB Output is correct
8 Correct 180 ms 262752 KB Output is correct
9 Correct 173 ms 262664 KB Output is correct
10 Correct 154 ms 257476 KB Output is correct
11 Correct 144 ms 255604 KB Output is correct
12 Incorrect 125 ms 251184 KB Output isn't correct
13 Halted 0 ms 0 KB -