oj.uz

Submission #522717

# Submission time Handle Problem Language Result Execution time Memory
522717 2022-02-05T14:23:03 Z CPSC Examination (JOI19_examination) C++14
2 / 100
 3000 ms 113792 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 = 3e5 + 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;
    //cout<<a[id]<<" "<<b[id]<<endl;
    update(1,1,mx,a[id],b[id]);
}
main() {
    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:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | 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 47 ms 94212 KB Output is correct
2 Correct 47 ms 94200 KB Output is correct
3 Correct 47 ms 94148 KB Output is correct
4 Correct 51 ms 94264 KB Output is correct
5 Correct 60 ms 94256 KB Output is correct
6 Correct 48 ms 94264 KB Output is correct
7 Correct 2118 ms 108348 KB Output is correct
8 Correct 2094 ms 108376 KB Output is correct
9 Correct 2133 ms 108272 KB Output is correct
10 Correct 1300 ms 101612 KB Output is correct
11 Correct 2085 ms 100196 KB Output is correct
12 Correct 204 ms 94580 KB Output is correct
13 Correct 2067 ms 110184 KB Output is correct
14 Correct 2044 ms 110156 KB Output is correct
15 Correct 2068 ms 110140 KB Output is correct
16 Correct 1541 ms 99272 KB Output is correct
17 Correct 1394 ms 100984 KB Output is correct
18 Correct 69 ms 94700 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94212 KB Output is correct
2 Correct 47 ms 94200 KB Output is correct
3 Correct 47 ms 94148 KB Output is correct
4 Correct 51 ms 94264 KB Output is correct
5 Correct 60 ms 94256 KB Output is correct
6 Correct 48 ms 94264 KB Output is correct
7 Correct 2118 ms 108348 KB Output is correct
8 Correct 2094 ms 108376 KB Output is correct
9 Correct 2133 ms 108272 KB Output is correct
10 Correct 1300 ms 101612 KB Output is correct
11 Correct 2085 ms 100196 KB Output is correct
12 Correct 204 ms 94580 KB Output is correct
13 Correct 2067 ms 110184 KB Output is correct
14 Correct 2044 ms 110156 KB Output is correct
15 Correct 2068 ms 110140 KB Output is correct
16 Correct 1541 ms 99272 KB Output is correct
17 Correct 1394 ms 100984 KB Output is correct
18 Correct 69 ms 94700 KB Output is correct
19 Execution timed out 3029 ms 113792 KB Time limit exceeded
20 Halted 0 ms 0 KB -