QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#409941	#6334. Passport	Physics212303	100 ✓	878ms	184256kb	C++17	2.1kb	2024-05-12 22:16:44	2024-05-12 22:16:44

Judging History

你现在查看的是最新测评结果

[2024-05-12 22:16:44]
评测

测评结果：100
用时：878ms
内存：184256kb

查看

[2024-05-12 22:16:44]
提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
const int I=1e18;
class graph_with_segtree{
  private:
    int n;
    vector<pii> B;
    vector<vector<pii> > g;
    vector<int> U;
  public:
    inline void add_edge(int u,int v,int w){
      g[v].emplace_back(u,w);
    }
    graph_with_segtree(int N){
      n=N,B.resize(n<<2),g.resize(n*6),U.resize(n*6);
      function<void(int,int,int)> build=[&](int u,int l,int r){
        if(B[u]=make_pair(l,r);l==r){
          add_edge(u+(n<<1),l,0); return;
        }
        add_edge(u+(n<<1),(u<<1)+(n<<1),0);
        add_edge(u+(n<<1),(u<<1|1)+(n<<1),0);
        int m=l+r>>1;
        build(u<<1,l,m),build(u<<1|1,m+1,r);
      };
      build(1,0,n-1);
    }
    inline void add_range(int u,int l,int r,int x){
      if(B[u].first>r||B[u].second<l)return;
      if(l<=B[u].first&&B[u].second<=r){
        add_edge(x,u+(n<<1),0); return;
      }
      add_range(u<<1,l,r,x),add_range(u<<1|1,l,r,x);
    }
    inline void dijkstra(vector<pii> s,vector<int> &d){
      vector<bool> b(n*6);
      priority_queue<pii,vector<pii>,greater<> > q;
      for(auto [u,w]:s)
        d[u]=w,q.emplace(w,u);
      while(!q.empty()){
        int u=q.top().second; q.pop();
        if(b[u])continue; b[u]=true;
        for(auto [i,w]:g[u])
          if(d[i]>d[u]+w)
            q.emplace(d[i]=d[u]+w,i);
      }
    }
    inline vector<int> solve(){
      vector<int> d0(n*6,I),dn(n*6,I),d(n*6);
      dijkstra({make_pair(0,0)},d0);
      dijkstra({make_pair(n-1,0)},dn);
      vector<pii> s;
      for(int i=0;i<n*6;i++)
        d[i]=min(d0[i]+dn[i],I);
      for(int i=n;i<n<<1;i++)
        if(d[i]<I)s.emplace_back(i,d[i]);
      dijkstra(s,d);
      return d;
    }
};
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin>>n;
  graph_with_segtree t(n);
  for(int i=0;i<n;i++){
    int l,r; cin>>l>>r,l--,r--;
    t.add_edge(i,i+n,1),t.add_range(1,l,r,i+n);
  }
  auto d=t.solve();
  int q; cin>>q;
  while(q--){
    int u; cin>>u,u--;
    cout<<(d[u]==I?-1:d[u])<<'\n';
  }
  return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 0ms

memory: 3576kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 6

Accepted

time: 1ms

memory: 3584kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 6

Accepted

time: 878ms

memory: 175136kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 6

Accepted

time: 347ms

memory: 137892kb

input:

output:

result:

ok single line: '15219'

Test #5:

score: 6

Accepted

time: 170ms

memory: 127296kb

input:

output:

result:

ok single line: '199999'

Test #6:

score: 6

Accepted

time: 250ms

memory: 120740kb

input:

output:

result:

ok single line: '1'

Test #7:

score: 6

Accepted

time: 124ms

memory: 109468kb

input:

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 0ms

memory: 3516kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 16

Accepted

time: 1ms

memory: 3560kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 16

Accepted

time: 1ms

memory: 3584kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 16

Accepted

time: 0ms

memory: 3480kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 16

Accepted

time: 1ms

memory: 3520kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 16

Accepted

time: 1ms

memory: 3560kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 16

Accepted

time: 0ms

memory: 3708kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 16

Accepted

time: 1ms

memory: 3932kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 16

Accepted

time: 1ms

memory: 3784kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 16

Accepted

time: 1ms

memory: 3772kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 16

Accepted

time: 0ms

memory: 3940kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 5ms

memory: 4980kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 24

Accepted

time: 0ms

memory: 4956kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 24

Accepted

time: 5ms

memory: 5396kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 24

Accepted

time: 0ms

memory: 5304kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 24

Accepted

time: 3ms

memory: 4816kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 24

Accepted

time: 3ms

memory: 4620kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 24

Accepted

time: 2ms

memory: 4372kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 24

Accepted

time: 5ms

memory: 4824kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 24

Accepted

time: 0ms

memory: 4892kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 6ms

memory: 5068kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 8

Accepted

time: 0ms

memory: 5052kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 8

Accepted

time: 3ms

memory: 4832kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 8

Accepted

time: 3ms

memory: 4612kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 2500 lines

Test #32:

score: 8

Accepted

time: 5ms

memory: 4924kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 46

Accepted

Test #33:

score: 46

Accepted

time: 873ms

memory: 176180kb

input:

output:

result:

ok 196830 lines

Test #34:

score: 46

Accepted

time: 367ms

memory: 139132kb

input:

output:

result:

ok 199765 lines

Test #35:

score: 46

Accepted

time: 466ms

memory: 183632kb

input:

output:

result:

ok 199851 lines

Test #36:

score: 46

Accepted

time: 462ms

memory: 184256kb

input:

output:

result:

ok 199992 lines

Test #37:

score: 46

Accepted

time: 196ms

memory: 128168kb

input:

output:

result:

ok 200000 lines

Test #38:

score: 46

Accepted

time: 198ms

memory: 135400kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 200000 lines

Test #39:

score: 46

Accepted

time: 157ms

memory: 53644kb

input:

output:

result:

ok 74422 lines

Test #40:

score: 46

Accepted

time: 442ms

memory: 145368kb

input:

output:

result:

ok 198765 lines

Test #41:

score: 46

Accepted

time: 328ms

memory: 148996kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 199636 lines

Extra Test:

score: 0

Extra Test Passed