結果
問題 | No.1703 Much Matching |
ユーザー |
![]() |
提出日時 | 2021-10-08 22:30:58 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,251 ms / 2,000 ms |
コード長 | 1,726 bytes |
コンパイル時間 | 2,234 ms |
コンパイル使用メモリ | 78,688 KB |
実行使用メモリ | 88,140 KB |
最終ジャッジ日時 | 2024-07-23 05:14:37 |
合計ジャッジ時間 | 18,708 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import java.io.*;import java.util.*;class Main{public static void main(String args[])throws Exception{BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));StringBuilder sb=new StringBuilder();String s[]=bu.readLine().split(" ");int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]),q=Integer.parseInt(s[2]);int i;ArrayList<Integer> g[]=new ArrayList[n];for(i=0;i<n;i++) g[i]=new ArrayList<>();for(i=0;i<q;i++){s=bu.readLine().split(" ");int u=Integer.parseInt(s[0])-1,v=Integer.parseInt(s[1])-1;g[u].add(v);}int ans=0;Queue<Integer> tem=new LinkedList<>();st=new int[4*m];for(i=0;i<n;i++){for(int x:g[i]){int cur=query(0,m-1,0,x-1,0);cur++;tem.add(cur);ans=Math.max(ans,cur);}for(int x:g[i]) update(0,m-1,x,tem.poll(),0);}System.out.println(ans);}static int st[];static void update(int ss,int se,int i,int v,int n){if(ss>se) return;if(ss==se){st[n]=Math.max(st[n],v);return;}int m=(se+ss)>>1;if(i<=m) update(ss,m,i,v,2*n+1);else update(m+1,se,i,v,2*n+2);st[n]=Math.max(st[2*n+1],st[2*n+2]);}static int query(int ss,int se,int qs,int qe,int n){if(ss>se || qs>se || qe<ss) return 0;if(qs<=ss && qe>=se) return st[n];int m=(se+ss)>>1;return Math.max(query(ss,m,qs,qe,2*n+1),query(m+1,se,qs,qe,2*n+2));}}