oj.uz

Submission #262603

# Submission time Handle Problem Language Result Execution time Memory
262603 2020-08-13T05:11:05 Z 문홍윤(#5091) Pairs (IOI07_pairs) C++17
60 / 100
 67 ms 4340 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int n, d, m;

void solve_1d(){
    vector<int> out, qu;
    for(int i=1; i<=n; i++){
        int p;
        scanf("%d", &p);
        out.eb(min(p+d+1, m+1));
        qu.eb(p);
    }
    svec(qu); svec(out);
    LL num=0, ans=0;
    int pv=0;
    for(auto i:qu){
        for(; pv<out.size(); pv++){
            if(out[pv]>i)break;
            num--;
        }
        ans+=num;
        num++;
    }
    printf("%lld", ans);
}

struct FENWICK{
    LL tree[150010];
    LL sum(int i){
        LL ans=0;
        while(i){
            ans+=tree[i];
            i-=(i&-i);
        }
        return ans;
    }
    void update(int i, LL num){
        while(i<=150000){
            tree[i]+=num;
            i+=(i&-i);
        }
    }
}fen;

void solve_2d(){
    vector<pii> out, qu;
    m*=2;
    for(int i=1; i<=n; i++){
        int p1, p2;
        scanf("%d %d", &p1, &p2);
        out.eb(min(p1+p2+d+1, m+1), p1-p2+m/2);
        qu.eb(p1+p2, p1-p2+m/2);
    }
    svec(qu); svec(out);
    LL ans=0;
    int pv=0;
    for(auto i:qu){
        for(; pv<out.size(); pv++){
            if(out[pv].F>i.F)break;
            fen.update(out[pv].S, -1);
        }
        ans+=fen.sum(min(i.S+d, m))-fen.sum(max(i.S-d-1, 0));
        fen.update(i.S, 1);
    }
    printf("%lld", ans);
}

void solve_3d(){

}

int main(){
    int dim;
    scanf("%d", &dim);
    scanf("%d %d %d", &n, &d, &m);
    if(dim==1)solve_1d();
    if(dim==2)solve_2d();
    if(dim==3)solve_3d();
}

/*
2 5 4 10
5 2
7 2
8 4
6 5
4 4
*/

Compilation message

pairs.cpp: In function 'void solve_1d()':
pairs.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(; pv<out.size(); pv++){
      |               ~~^~~~~~~~~~~
pairs.cpp: In function 'void solve_2d()':
pairs.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(; pv<out.size(); pv++){
      |               ~~^~~~~~~~~~~
pairs.cpp: In function 'void solve_1d()':
pairs.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |         scanf("%d", &p);
      |         ~~~~~^~~~~~~~~~
pairs.cpp: In function 'void solve_2d()':
pairs.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |         scanf("%d %d", &p1, &p2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |     scanf("%d", &dim);
      |     ~~~~~^~~~~~~~~~~~
pairs.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |     scanf("%d %d %d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 256 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1276 KB Output is correct
2 Correct 22 ms 1336 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1276 KB Output is correct
2 Correct 29 ms 1276 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1276 KB Output is correct
2 Correct 36 ms 1276 KB Output is correct
3 Correct 33 ms 1276 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1408 KB Output is correct
2 Correct 2 ms 1408 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2152 KB Output is correct
2 Correct 45 ms 2784 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 2148 KB Output is correct
2 Correct 61 ms 3084 KB Output is correct
3 Correct 67 ms 3044 KB Output is correct
4 Correct 56 ms 2916 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3168 KB Output is correct
2 Correct 60 ms 4324 KB Output is correct
3 Correct 66 ms 4340 KB Output is correct
4 Correct 57 ms 4320 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -