oj.uz

Submission #522744

# Submission time Handle Problem Language Result Execution time Memory
522744 2022-02-05T15:56:50 Z CPSC Examination (JOI19_examination) C++14
2 / 100
 3000 ms 332532 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 = 1e5 + 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,shes1;
vector <int> tocomp,tocomp1;
int mx1,cnt1;
multiset <int> ms,ms1;
unordered_map <int, int> tree[4*N];
vector < pii > v,v1;
void updatefenw(int node, int idx, int val) {
    for (int i = idx; i <= mx1; 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) {
    for (int i = idx; i <= mx; i+=i&(-i)) {
        updatefenw(i,val,1);
    }
}
int getans(int node, int le, int ri, int start, int end, int val1) {
    int pas = 0;
    for (int i = end; i > 0; i -= i&(-i)){
        pas += getfenw(i,val1,mx1);
    }
    for (int i = start - 1; i > 0; i-=i&(-i)) {
        pas -= getfenw(i,val1,mx1);
    }
    return pas;
}
void add(int idx) {
    id = v[idx].s;
    update(1,1,mx,a[id],b[id]);
}
signed 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]);
        tocomp1.pb(b[i]);
        ms.insert(a[i]);
        ms1.insert(b[i]);
        v.pb({a[i] + b[i],i});
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    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;
    }
    sort(tocomp1.begin(),tocomp1.end());
    cnt1 = 1;
    shes1[tocomp1[0]] = 1;
    for (int i = 1; i < tocomp1.size(); i++) {
        if (tocomp1[i] != tocomp1[i - 1]) cnt1++;
        mx1 = cnt1;
        shes1[tocomp1[i]] = cnt1;
    }
    int ss = 1e9 + 3;
    for (int i = 1; i <= q; i++) {
        cin>>x[i]>>y[i]>>z[i];
        if (ms.lower_bound(x[i]) != ms.end())
        x[i] = *ms.lower_bound(x[i]); else x[i] = ss;
        if (ms1.lower_bound(y[i]) != ms1.end())
        y[i] = *ms1.lower_bound(y[i]); else y[i] = ss;
        v1.pb({z[i],i});
    }
    
    for (int i = 1; i <= n; i++) {
        a[i] = shes[a[i]];
        b[i] = shes1[b[i]];
    }for (int i = 1; i <= q; i++) {
        if (x[i] != ss)
        x[i] = shes[x[i]]; 
        if (y[i] != ss) y[i] = shes1[y[i]];
    }
    
    sort(v1.begin(),v1.end());
    reverse(v1.begin(),v1.end());
    //if (n >= 100000) assert(false);
    cur = 0;
    for(int i = 0; i < v1.size(); i++) {
        if (x[v1[i].s] == ss || y[v1[i].s] == ss) {
            pas[v1[i].s] = 0; continue;
        }
        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 <= q; i++) cout<<pas[i]<<" ";
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 1; i < tocomp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
examination.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 1; i < tocomp1.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
examination.cpp:102: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]
  102 |     for(int i = 0; i < v1.size(); i++) {
      |                    ~~^~~~~~~~~~~
examination.cpp:106: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]
  106 |         while (cur < v.size() && v[cur].f >= v1[i].f) {
      |                ~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22256 KB Output is correct
2 Correct 12 ms 22260 KB Output is correct
3 Correct 12 ms 22208 KB Output is correct
4 Correct 12 ms 22192 KB Output is correct
5 Correct 12 ms 22224 KB Output is correct
6 Correct 12 ms 22220 KB Output is correct
7 Correct 46 ms 28416 KB Output is correct
8 Correct 43 ms 28492 KB Output is correct
9 Correct 43 ms 28516 KB Output is correct
10 Correct 21 ms 23660 KB Output is correct
11 Correct 20 ms 23500 KB Output is correct
12 Correct 17 ms 22656 KB Output is correct
13 Correct 46 ms 28584 KB Output is correct
14 Correct 48 ms 28492 KB Output is correct
15 Correct 45 ms 28484 KB Output is correct
16 Correct 17 ms 22988 KB Output is correct
17 Correct 19 ms 23204 KB Output is correct
18 Correct 15 ms 22732 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3099 ms 332532 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 3099 ms 332532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22256 KB Output is correct
2 Correct 12 ms 22260 KB Output is correct
3 Correct 12 ms 22208 KB Output is correct
4 Correct 12 ms 22192 KB Output is correct
5 Correct 12 ms 22224 KB Output is correct
6 Correct 12 ms 22220 KB Output is correct
7 Correct 46 ms 28416 KB Output is correct
8 Correct 43 ms 28492 KB Output is correct
9 Correct 43 ms 28516 KB Output is correct
10 Correct 21 ms 23660 KB Output is correct
11 Correct 20 ms 23500 KB Output is correct
12 Correct 17 ms 22656 KB Output is correct
13 Correct 46 ms 28584 KB Output is correct
14 Correct 48 ms 28492 KB Output is correct
15 Correct 45 ms 28484 KB Output is correct
16 Correct 17 ms 22988 KB Output is correct
17 Correct 19 ms 23204 KB Output is correct
18 Correct 15 ms 22732 KB Output is correct
19 Execution timed out 3099 ms 332532 KB Time limit exceeded
20 Halted 0 ms 0 KB -