oj.uz

Submission #522718

# Submission time Handle Problem Language Result Execution time Memory
522718 2022-02-05T14:24:28 Z CPSC Examination (JOI19_examination) C++14
2 / 100
 3000 ms 174420 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> 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);
    vec[node] = vec[2*node];
    tree[node] = tree[2*node];
    for (int i = 0; i < vec[2*node + 1].size(); i++) {
        vec[node].pb({vec[2*node + 1][i].f, vec[2*node +1][i].s});
        updatefenw(node, vec[2*node + 1][i].f, vec[2*node + 1][i].s);
    }
    
}
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) {
        return getfenw(node,val1,mx);
    }
    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]);
}
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 <= q; i++) cout<<pas[i]<<" ";
}

Compilation message

examination.cpp: In function 'void update(int, int, int, int, int)':
examination.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < vec[2*node + 1].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main() {
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 1; i < tocomp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
examination.cpp:92: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]
   92 |     for(int i = 0; i < v1.size(); i++) {
      |                    ~~^~~~~~~~~~~
examination.cpp:93: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]
   93 |         while (cur < v.size() && v[cur].f >= v1[i].f) {
      |                ~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 156908 KB Output is correct
2 Correct 77 ms 156868 KB Output is correct
3 Correct 78 ms 156888 KB Output is correct
4 Correct 83 ms 156872 KB Output is correct
5 Correct 77 ms 157000 KB Output is correct
6 Correct 77 ms 156872 KB Output is correct
7 Correct 2021 ms 170864 KB Output is correct
8 Correct 2045 ms 171068 KB Output is correct
9 Correct 2122 ms 170732 KB Output is correct
10 Correct 1309 ms 164280 KB Output is correct
11 Correct 2080 ms 162716 KB Output is correct
12 Correct 226 ms 157252 KB Output is correct
13 Correct 2017 ms 172816 KB Output is correct
14 Correct 2023 ms 172700 KB Output is correct
15 Correct 2001 ms 172868 KB Output is correct
16 Correct 1524 ms 161960 KB Output is correct
17 Correct 1406 ms 163568 KB Output is correct
18 Correct 85 ms 157276 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 156908 KB Output is correct
2 Correct 77 ms 156868 KB Output is correct
3 Correct 78 ms 156888 KB Output is correct
4 Correct 83 ms 156872 KB Output is correct
5 Correct 77 ms 157000 KB Output is correct
6 Correct 77 ms 156872 KB Output is correct
7 Correct 2021 ms 170864 KB Output is correct
8 Correct 2045 ms 171068 KB Output is correct
9 Correct 2122 ms 170732 KB Output is correct
10 Correct 1309 ms 164280 KB Output is correct
11 Correct 2080 ms 162716 KB Output is correct
12 Correct 226 ms 157252 KB Output is correct
13 Correct 2017 ms 172816 KB Output is correct
14 Correct 2023 ms 172700 KB Output is correct
15 Correct 2001 ms 172868 KB Output is correct
16 Correct 1524 ms 161960 KB Output is correct
17 Correct 1406 ms 163568 KB Output is correct
18 Correct 85 ms 157276 KB Output is correct
19 Execution timed out 3077 ms 174420 KB Time limit exceeded
20 Halted 0 ms 0 KB -