oj.uz

답안 #895902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895902 2023-12-31T04:13:19 Z 1075508020060209tc Two Antennas (JOI19_antennas) C++14
13 / 100
 1402 ms 524288 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
struct SGTR{
int l;int r;int mx;
}tr[800005];
void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
tr[nw].mx=-1;
if(l==r){
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
}
void upd(int nw,int pl,int v){
if(tr[nw].l==pl&&tr[nw].r==pl){
    tr[nw].mx=max(tr[nw].mx,v);
    return;
}
if(tr[nw].l>pl||tr[nw].r<pl){return;}
upd(nw*2,pl,v);
upd(nw*2+1,pl,v);
tr[nw].mx=max(tr[nw*2].mx,tr[nw*2+1].mx);
}
int qmx(int nw,int pl){
if(tr[nw].l>=pl){
    return tr[nw].mx;
}
if(tr[nw].r<pl){
    return -1;
}
return max(qmx(nw*2,pl),qmx(nw*2+1,pl));
}


int n;int Q;
int ar[500005];
int br[500005];
int hr[500005];
int lar[500005];
int rar[500005];
vector<pair<int,int>>e[500005];
vector<int>qe[500005];
int ans[500005];
signed main(){

cin>>n;
for(int i=1;i<=n;i++){
    cin>>hr[i]>>ar[i]>>br[i];
}
cin>>Q;
for(int i=1;i<=Q;i++){
    cin>>lar[i]>>rar[i];
    qe[rar[i]].push_back(i);
}
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        int d=abs(i-j);
        if(d>=ar[i]&&d<=br[i]&&d>=ar[j]&&d<=br[j]){
            e[j].push_back({i,abs(hr[i]-hr[j])});
        }
    }
}
buildtr(1,1,n);
for(int i=1;i<=n;i++){
    for(int j=0;j<e[i].size();j++){
        upd(1,e[i][j].first,e[i][j].second);
    }
    for(int j=0;j<qe[i].size();j++){
        int id=qe[i][j];
        ans[id]=qmx(1,lar[id]);
    }
}
for(int i=1;i<=Q;i++){
    cout<<ans[i]<<"\n";
}

}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:71:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int j=0;j<e[i].size();j++){
      |                 ~^~~~~~~~~~~~
antennas.cpp:74:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int j=0;j<qe[i].size();j++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 37212 KB Output is correct
2 Correct 9 ms 37468 KB Output is correct
3 Correct 9 ms 37212 KB Output is correct
4 Correct 9 ms 37496 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct
6 Correct 9 ms 37468 KB Output is correct
7 Correct 9 ms 37296 KB Output is correct
8 Correct 9 ms 37332 KB Output is correct
9 Correct 8 ms 37212 KB Output is correct
10 Correct 9 ms 37340 KB Output is correct
11 Correct 8 ms 37208 KB Output is correct
12 Correct 9 ms 37468 KB Output is correct
13 Correct 8 ms 37212 KB Output is correct
14 Correct 9 ms 37212 KB Output is correct
15 Correct 9 ms 37400 KB Output is correct
16 Correct 9 ms 37212 KB Output is correct
17 Correct 11 ms 37368 KB Output is correct
18 Correct 9 ms 37208 KB Output is correct
19 Correct 8 ms 37212 KB Output is correct
20 Correct 9 ms 37408 KB Output is correct
21 Correct 9 ms 37384 KB Output is correct
22 Correct 9 ms 37212 KB Output is correct
23 Correct 9 ms 37208 KB Output is correct
24 Correct 10 ms 37332 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 37212 KB Output is correct
2 Correct 9 ms 37468 KB Output is correct
3 Correct 9 ms 37212 KB Output is correct
4 Correct 9 ms 37496 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct
6 Correct 9 ms 37468 KB Output is correct
7 Correct 9 ms 37296 KB Output is correct
8 Correct 9 ms 37332 KB Output is correct
9 Correct 8 ms 37212 KB Output is correct
10 Correct 9 ms 37340 KB Output is correct
11 Correct 8 ms 37208 KB Output is correct
12 Correct 9 ms 37468 KB Output is correct
13 Correct 8 ms 37212 KB Output is correct
14 Correct 9 ms 37212 KB Output is correct
15 Correct 9 ms 37400 KB Output is correct
16 Correct 9 ms 37212 KB Output is correct
17 Correct 11 ms 37368 KB Output is correct
18 Correct 9 ms 37208 KB Output is correct
19 Correct 8 ms 37212 KB Output is correct
20 Correct 9 ms 37408 KB Output is correct
21 Correct 9 ms 37384 KB Output is correct
22 Correct 9 ms 37212 KB Output is correct
23 Correct 9 ms 37208 KB Output is correct
24 Correct 10 ms 37332 KB Output is correct
25 Correct 86 ms 44136 KB Output is correct
26 Correct 33 ms 42588 KB Output is correct
27 Correct 121 ms 51540 KB Output is correct
28 Correct 136 ms 52468 KB Output is correct
29 Correct 82 ms 44492 KB Output is correct
30 Correct 92 ms 48720 KB Output is correct
31 Correct 93 ms 46672 KB Output is correct
32 Correct 128 ms 52564 KB Output is correct
33 Correct 108 ms 50308 KB Output is correct
34 Correct 77 ms 47228 KB Output is correct
35 Correct 116 ms 50852 KB Output is correct
36 Correct 129 ms 52532 KB Output is correct
37 Correct 76 ms 44444 KB Output is correct
38 Correct 112 ms 48692 KB Output is correct
39 Correct 25 ms 42332 KB Output is correct
40 Correct 111 ms 48720 KB Output is correct
41 Correct 89 ms 45140 KB Output is correct
42 Correct 109 ms 48584 KB Output is correct
43 Correct 53 ms 43324 KB Output is correct
44 Correct 113 ms 48704 KB Output is correct
45 Correct 31 ms 42584 KB Output is correct
46 Correct 114 ms 48724 KB Output is correct
47 Correct 37 ms 42836 KB Output is correct
48 Correct 121 ms 48784 KB Output is correct

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1402 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 37212 KB Output is correct
2 Correct 9 ms 37468 KB Output is correct
3 Correct 9 ms 37212 KB Output is correct
4 Correct 9 ms 37496 KB Output is correct
5 Correct 9 ms 37212 KB Output is correct
6 Correct 9 ms 37468 KB Output is correct
7 Correct 9 ms 37296 KB Output is correct
8 Correct 9 ms 37332 KB Output is correct
9 Correct 8 ms 37212 KB Output is correct
10 Correct 9 ms 37340 KB Output is correct
11 Correct 8 ms 37208 KB Output is correct
12 Correct 9 ms 37468 KB Output is correct
13 Correct 8 ms 37212 KB Output is correct
14 Correct 9 ms 37212 KB Output is correct
15 Correct 9 ms 37400 KB Output is correct
16 Correct 9 ms 37212 KB Output is correct
17 Correct 11 ms 37368 KB Output is correct
18 Correct 9 ms 37208 KB Output is correct
19 Correct 8 ms 37212 KB Output is correct
20 Correct 9 ms 37408 KB Output is correct
21 Correct 9 ms 37384 KB Output is correct
22 Correct 9 ms 37212 KB Output is correct
23 Correct 9 ms 37208 KB Output is correct
24 Correct 10 ms 37332 KB Output is correct
25 Correct 86 ms 44136 KB Output is correct
26 Correct 33 ms 42588 KB Output is correct
27 Correct 121 ms 51540 KB Output is correct
28 Correct 136 ms 52468 KB Output is correct
29 Correct 82 ms 44492 KB Output is correct
30 Correct 92 ms 48720 KB Output is correct
31 Correct 93 ms 46672 KB Output is correct
32 Correct 128 ms 52564 KB Output is correct
33 Correct 108 ms 50308 KB Output is correct
34 Correct 77 ms 47228 KB Output is correct
35 Correct 116 ms 50852 KB Output is correct
36 Correct 129 ms 52532 KB Output is correct
37 Correct 76 ms 44444 KB Output is correct
38 Correct 112 ms 48692 KB Output is correct
39 Correct 25 ms 42332 KB Output is correct
40 Correct 111 ms 48720 KB Output is correct
41 Correct 89 ms 45140 KB Output is correct
42 Correct 109 ms 48584 KB Output is correct
43 Correct 53 ms 43324 KB Output is correct
44 Correct 113 ms 48704 KB Output is correct
45 Correct 31 ms 42584 KB Output is correct
46 Correct 114 ms 48724 KB Output is correct
47 Correct 37 ms 42836 KB Output is correct
48 Correct 121 ms 48784 KB Output is correct
49 Runtime error 1402 ms 524288 KB Execution killed with signal 9
50 Halted 0 ms 0 KB -