oj.uz

Submission #522745

# Submission time Handle Problem Language Result Execution time Memory
522745 2022-02-05T15:58:14 Z CPSC Examination (JOI19_examination) C++14
2 / 100
 3000 ms 324244 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
#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;
map <int, int> tree[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.rbegin(),v1.rend());
    //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:67:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 1; i < tocomp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
examination.cpp:75:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 1; i < tocomp1.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
examination.cpp:102:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long 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: 'long long int' and 'std::vector<std::pair<long long int, long long 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 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 58 ms 13904 KB Output is correct
8 Correct 61 ms 13996 KB Output is correct
9 Correct 65 ms 13892 KB Output is correct
10 Correct 16 ms 6732 KB Output is correct
11 Correct 27 ms 6760 KB Output is correct
12 Correct 8 ms 5636 KB Output is correct
13 Correct 63 ms 14016 KB Output is correct
14 Correct 61 ms 13876 KB Output is correct
15 Correct 63 ms 14020 KB Output is correct
16 Correct 8 ms 5836 KB Output is correct
17 Correct 9 ms 5888 KB Output is correct
18 Correct 6 ms 5580 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 58 ms 13904 KB Output is correct
8 Correct 61 ms 13996 KB Output is correct
9 Correct 65 ms 13892 KB Output is correct
10 Correct 16 ms 6732 KB Output is correct
11 Correct 27 ms 6760 KB Output is correct
12 Correct 8 ms 5636 KB Output is correct
13 Correct 63 ms 14016 KB Output is correct
14 Correct 61 ms 13876 KB Output is correct
15 Correct 63 ms 14020 KB Output is correct
16 Correct 8 ms 5836 KB Output is correct
17 Correct 9 ms 5888 KB Output is correct
18 Correct 6 ms 5580 KB Output is correct
19 Execution timed out 3110 ms 324244 KB Time limit exceeded
20 Halted 0 ms 0 KB -