oj.uz

Submission #262623

# Submission time Handle Problem Language Result Execution time Memory
262623 2020-08-13T05:49:52 Z 반딧불(#5089) Pairs (IOI07_pairs) C++17
42 / 100
 179 ms 13656 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Query{
    int x, y, t; /// t: 0 (start), 1 (mid), 2 (end)
    Query(){}
    Query(int x, int y, int t): x(x), y(y), t(t){}

    bool operator<(const Query &r)const{
        if(y != r.y) return y<r.y;
        return t<r.t;
    }
};

ll tree[1200002], lazy[1200002];
void propagate(int i, int l, int r){
    if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
    else tree[i] += lazy[i] * (r-l+1);
    lazy[i] = 0;
}

void addTree(int i, int l, int r, int s, int e, ll val){
    propagate(i, l, r);
    if(l==s && r==e){
        lazy[i] += val;
        propagate(i, l, r);
        return;
    }
    int m = (l+r)>>1;
    if(s<=m) addTree(i*2, l, m, s, min(m, e), val);
    if(m<e) addTree(i*2+1, m+1, r, max(s, m+1), e, val);
}
ll getTree(int i, int l, int r, int idx){
    propagate(i, l, r);
    if(l==r) return tree[i];
    int m = (l+r)>>1;
    if(idx<=m) return getTree(i*2, l, m, idx);
    return getTree(i*2+1, m+1, r, idx);
}

int b, n, d, m;
int x[100002], y[100002], z[100002];
ll ans;
vector<Query> vec;

int main(){
    scanf("%d %d %d %d", &b, &n, &d, &m);
    for(int i=1; i<=n; i++){
        if(b>=1) scanf("%d", &x[i]);
        if(b>=2) scanf("%d", &y[i]);
        if(b>=3) scanf("%d", &z[i]);
    }

    for(int i=1; i<=n; i++){
        vec.push_back({x[i]+y[i], x[i]-y[i]-d, 0});
        vec.push_back({x[i]+y[i], x[i]-y[i], 1});
        vec.push_back({x[i]+y[i], x[i]-y[i]+d, 2});
    }
    sort(vec.begin(), vec.end());

    for(auto tmp: vec){
        if(tmp.t == 0) addTree(1, 1, 300000, max(1, tmp.x-d), min(300000, tmp.x+d), 1);
        else if(tmp.t == 2) addTree(1, 1, 300000, max(1, tmp.x-d), min(300000, tmp.x+d), -1);
        else ans += getTree(1, 1, 300000, tmp.x);
    }
    printf("%lld", (ans-n)/2);
}

Compilation message

pairs.cpp: In function 'int main()':
pairs.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d %d %d %d", &b, &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:52:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         if(b>=1) scanf("%d", &x[i]);
      |                  ~~~~~^~~~~~~~~~~~~
pairs.cpp:53:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         if(b>=2) scanf("%d", &y[i]);
      |                  ~~~~~^~~~~~~~~~~~~
pairs.cpp:54:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         if(b>=3) scanf("%d", &z[i]);
      |                  ~~~~~^~~~~~~~~~~~~

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 384 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 768 KB Output isn't correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 7024 KB Output is correct
2 Correct 91 ms 7024 KB Output is correct

Subtask #4
0 / 6.0

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

Subtask #5
0 / 6.0

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

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5632 KB Output is correct
2 Correct 5 ms 6144 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 7408 KB Output is correct
2 Correct 97 ms 7400 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 7400 KB Output is correct
2 Correct 122 ms 7400 KB Output is correct
3 Correct 121 ms 7536 KB Output is correct
4 Correct 120 ms 7400 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 11836 KB Output is correct
2 Correct 177 ms 13656 KB Output is correct
3 Correct 139 ms 12832 KB Output is correct
4 Correct 137 ms 12248 KB Output is correct

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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