oj.uz

답안 #522719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522719 2022-02-05T14:27:08 Z CPSC Examination (JOI19_examination) C++14
2 / 100
 3000 ms 558300 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);
    if (le <= idx && ri >= idx) {
        vec[node].pb({val,1});
         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) {
        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:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main() {
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 1; i < tocomp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
examination.cpp:89: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]
   89 |     for(int i = 0; i < v1.size(); i++) {
      |                    ~~^~~~~~~~~~~
examination.cpp:90: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]
   90 |         while (cur < v.size() && v[cur].f >= v1[i].f) {
      |                ~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 156996 KB Output is correct
2 Correct 87 ms 156916 KB Output is correct
3 Correct 90 ms 156844 KB Output is correct
4 Correct 77 ms 156900 KB Output is correct
5 Correct 77 ms 156816 KB Output is correct
6 Correct 80 ms 156868 KB Output is correct
7 Correct 145 ms 172640 KB Output is correct
8 Correct 186 ms 172740 KB Output is correct
9 Correct 166 ms 172612 KB Output is correct
10 Correct 114 ms 164388 KB Output is correct
11 Correct 109 ms 162356 KB Output is correct
12 Correct 86 ms 157264 KB Output is correct
13 Correct 156 ms 172748 KB Output is correct
14 Correct 165 ms 172776 KB Output is correct
15 Correct 164 ms 172616 KB Output is correct
16 Correct 130 ms 161656 KB Output is correct
17 Correct 109 ms 163672 KB Output is correct
18 Correct 86 ms 157292 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3099 ms 558300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3099 ms 558300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 156996 KB Output is correct
2 Correct 87 ms 156916 KB Output is correct
3 Correct 90 ms 156844 KB Output is correct
4 Correct 77 ms 156900 KB Output is correct
5 Correct 77 ms 156816 KB Output is correct
6 Correct 80 ms 156868 KB Output is correct
7 Correct 145 ms 172640 KB Output is correct
8 Correct 186 ms 172740 KB Output is correct
9 Correct 166 ms 172612 KB Output is correct
10 Correct 114 ms 164388 KB Output is correct
11 Correct 109 ms 162356 KB Output is correct
12 Correct 86 ms 157264 KB Output is correct
13 Correct 156 ms 172748 KB Output is correct
14 Correct 165 ms 172776 KB Output is correct
15 Correct 164 ms 172616 KB Output is correct
16 Correct 130 ms 161656 KB Output is correct
17 Correct 109 ms 163672 KB Output is correct
18 Correct 86 ms 157292 KB Output is correct
19 Execution timed out 3099 ms 558300 KB Time limit exceeded
20 Halted 0 ms 0 KB -