Submission #1387228
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- int N,Q; int A[101010],B[101010],C[101010]; int D[101010],E[101010]; vector<int> ev[101010]; int minm; int sum[101010]; int num[101010]; int ng[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]>>B[i]; FOR(i,N+1) cin>>C[i]; sort(C,C+N+1); FOR(i,N) { B[i]=min(A[i],B[i]); A[i]=lower_bound(C,C+N+1,A[i])-C; B[i]=lower_bound(C,C+N+1,B[i])-C; if(B[i]<A[i]) ev[B[i]].push_back(i); } minm=N+2; FOR(i,N+1) sum[i]=-1; FOR(i,N) sum[A[i]]++; priority_queue<pair<int,int>> P; vector<vector<int>> seg; int ret=N; FOR(i,N+1) { if(i) sum[i]+=sum[i-1], ng[i]+=ng[i-1]; FORR(e,ev[i]) P.push({A[e],e}); while(sum[i]<0 && P.size()) { int x=P.top().second; P.pop(); sum[i]++; sum[A[x]]--; seg.push_back({i,A[x]}); ret--; } if(sum[i]==-1) { minm=min(minm,i); ng[i]++; } if(sum[i]<-1) minm=-1; } int minL=N+2; for(i=seg.size()-1;i>=0;i--) { if(ng[seg[i][1]-1]==((seg[i][0])?ng[seg[i][0]-1]:0) && seg[i][1]<=minL) { num[seg[i][0]]++; minL=seg[i][0]; } } for(i=N+1;i>=0;i--) num[i]+=num[i+1]; cin>>Q; FOR(i,Q) { cin>>x>>y; x=lower_bound(C,C+N+1,x)-C; y=lower_bound(C,C+N+1,y)-C; //cout<<x<<y<<" : "; int rx=(minm<x)?-1:(N-seg.size()+(num[x]+1)); int ry=(minm<y)?-1:(N-seg.size()+num[y]); cout<<max(rx,ry)<<endl; } } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false), cin.tie(0); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Two Faced Cards |
User | kmjp |
Language | C++14 (GCC 5.4.1) |
Score | 2000 |
Code Size | 2091 Byte |
Status | AC |
Exec Time | 290 ms |
Memory | 15152 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 2000 / 2000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 3 ms | 3200 KB |
sample_02.txt | AC | 2 ms | 3200 KB |
sample_03.txt | AC | 2 ms | 3200 KB |
subtask_1_01.txt | AC | 69 ms | 5764 KB |
subtask_1_02.txt | AC | 142 ms | 9268 KB |
subtask_1_03.txt | AC | 46 ms | 4608 KB |
subtask_1_04.txt | AC | 76 ms | 11700 KB |
subtask_1_05.txt | AC | 119 ms | 4744 KB |
subtask_1_06.txt | AC | 212 ms | 12596 KB |
subtask_1_07.txt | AC | 137 ms | 14644 KB |
subtask_1_08.txt | AC | 125 ms | 14384 KB |
subtask_1_09.txt | AC | 150 ms | 7424 KB |
subtask_1_10.txt | AC | 78 ms | 9396 KB |
subtask_1_11.txt | AC | 75 ms | 8884 KB |
subtask_1_12.txt | AC | 81 ms | 8244 KB |
subtask_1_13.txt | AC | 152 ms | 6008 KB |
subtask_1_14.txt | AC | 58 ms | 7864 KB |
subtask_1_15.txt | AC | 80 ms | 12084 KB |
subtask_1_16.txt | AC | 81 ms | 5308 KB |
subtask_1_17.txt | AC | 243 ms | 8820 KB |
subtask_1_18.txt | AC | 32 ms | 7736 KB |
subtask_1_19.txt | AC | 236 ms | 9908 KB |
subtask_1_20.txt | AC | 181 ms | 13360 KB |
subtask_1_21.txt | AC | 267 ms | 7800 KB |
subtask_1_22.txt | AC | 286 ms | 14768 KB |
subtask_1_23.txt | AC | 272 ms | 7800 KB |
subtask_1_24.txt | AC | 276 ms | 14768 KB |
subtask_1_25.txt | AC | 277 ms | 9076 KB |
subtask_1_26.txt | AC | 279 ms | 14640 KB |
subtask_1_27.txt | AC | 279 ms | 14384 KB |
subtask_1_28.txt | AC | 279 ms | 14768 KB |
subtask_1_29.txt | AC | 269 ms | 9076 KB |
subtask_1_30.txt | AC | 275 ms | 14640 KB |
subtask_1_31.txt | AC | 276 ms | 14512 KB |
subtask_1_32.txt | AC | 289 ms | 14896 KB |
subtask_1_33.txt | AC | 270 ms | 9096 KB |
subtask_1_34.txt | AC | 278 ms | 15024 KB |
subtask_1_35.txt | AC | 275 ms | 14640 KB |
subtask_1_36.txt | AC | 279 ms | 14896 KB |
subtask_1_37.txt | AC | 278 ms | 8948 KB |
subtask_1_38.txt | AC | 280 ms | 15152 KB |
subtask_1_39.txt | AC | 280 ms | 14384 KB |
subtask_1_40.txt | AC | 290 ms | 14768 KB |
subtask_1_41.txt | AC | 251 ms | 7176 KB |
subtask_1_42.txt | AC | 245 ms | 6972 KB |
subtask_1_43.txt | AC | 250 ms | 7796 KB |
subtask_1_44.txt | AC | 246 ms | 7608 KB |
subtask_1_45.txt | AC | 246 ms | 7480 KB |
subtask_1_46.txt | AC | 237 ms | 7032 KB |
subtask_1_47.txt | AC | 238 ms | 6144 KB |
subtask_1_48.txt | AC | 241 ms | 7548 KB |
subtask_1_49.txt | AC | 244 ms | 6972 KB |
subtask_1_50.txt | AC | 234 ms | 6716 KB |
subtask_1_51.txt | AC | 2 ms | 3200 KB |
subtask_1_52.txt | AC | 2 ms | 3200 KB |
subtask_1_53.txt | AC | 2 ms | 3200 KB |
subtask_1_54.txt | AC | 2 ms | 3200 KB |
subtask_1_55.txt | AC | 2 ms | 3200 KB |