oj.uz

Submission #522737

# Submission time Handle Problem Language Result Execution time Memory
522737 2022-02-05T15:07:15 Z CPSC Examination (JOI19_examination) C++14
2 / 100
 3000 ms 390064 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) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        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) {
         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) {
        //cout<<le<<" "<<ri<<" "<<val1<<" '"
        return getfenw(node,val1,mx1);
    }
    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() {
    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]];
        //i//f (x[i] == ss) cout<<i<<endl;
    }
    sort(v1.begin(),v1.end());
    reverse(v1.begin(),v1.end());
    cur = 0;
    for(int i = 0; i < v1.size(); i++) {
        if (x[v1[i].s] == ss || y[v1[i].s] == ss) {
          //  cout<<v1[i].s<<" "<<x[i]<<" "<<y[i]<<endl;
            pas[v1[i].s] = 0; continue;
        }
        while (cur < v.size() && v[cur].f >= v1[i].f) {
           // cout<<v[cur].s<<endl;
            add(cur);
            cur++;
        }
        //cout<<x[v1[i].s]<<"   "<<y[v1[i].s]<<endl;
        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:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main() {
      | ^~~~
examination.cpp: In function 'int main()':
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 < tocomp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
examination.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 1; i < tocomp1.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
examination.cpp:109: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]
  109 |     for(int i = 0; i < v1.size(); i++) {
      |                    ~~^~~~~~~~~~~
examination.cpp:114: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]
  114 |         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 22220 KB Output is correct
2 Correct 13 ms 22220 KB Output is correct
3 Correct 15 ms 22160 KB Output is correct
4 Correct 14 ms 22248 KB Output is correct
5 Correct 13 ms 22236 KB Output is correct
6 Correct 14 ms 22220 KB Output is correct
7 Correct 60 ms 31492 KB Output is correct
8 Correct 54 ms 31428 KB Output is correct
9 Correct 54 ms 31428 KB Output is correct
10 Correct 23 ms 24488 KB Output is correct
11 Correct 22 ms 24132 KB Output is correct
12 Correct 16 ms 22728 KB Output is correct
13 Correct 53 ms 31448 KB Output is correct
14 Correct 53 ms 31464 KB Output is correct
15 Correct 53 ms 31460 KB Output is correct
16 Correct 16 ms 22988 KB Output is correct
17 Correct 19 ms 23788 KB Output is correct
18 Correct 18 ms 22764 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 390064 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 3078 ms 390064 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 22220 KB Output is correct
2 Correct 13 ms 22220 KB Output is correct
3 Correct 15 ms 22160 KB Output is correct
4 Correct 14 ms 22248 KB Output is correct
5 Correct 13 ms 22236 KB Output is correct
6 Correct 14 ms 22220 KB Output is correct
7 Correct 60 ms 31492 KB Output is correct
8 Correct 54 ms 31428 KB Output is correct
9 Correct 54 ms 31428 KB Output is correct
10 Correct 23 ms 24488 KB Output is correct
11 Correct 22 ms 24132 KB Output is correct
12 Correct 16 ms 22728 KB Output is correct
13 Correct 53 ms 31448 KB Output is correct
14 Correct 53 ms 31464 KB Output is correct
15 Correct 53 ms 31460 KB Output is correct
16 Correct 16 ms 22988 KB Output is correct
17 Correct 19 ms 23788 KB Output is correct
18 Correct 18 ms 22764 KB Output is correct
19 Execution timed out 3078 ms 390064 KB Time limit exceeded
20 Halted 0 ms 0 KB -