Uva&LA部分题目代码

  1 #include <algorithm>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string>
  5 #include <queue>
  6 #include <map>
  7 #include <set>
  8 #include <ctime>
  9 #include <cmath>
 10 #include <iostream>
 11 #define pi acos(-1.)
 12 using namespace std;
 13 typedef long long ll;
 14 const int int_inf = 0x3f3f3f3f;
 15 const ll ll_inf = 1ll << 62;
 16 const int INT_INF = (int)((1ll << 31) - 1);
 17 const int mod = 1e6 + 7;
 18 const double double_inf = 1e30;
 19 typedef unsigned long long ul;
 20 #pragma comment(linker, "/STACK:102400000,102400000")
 21 #define max(a, b) ((a) > (b) ? (a) : (b))
 22 #define min(a, b) ((a) < (b) ? (a) : (b))
 23 #define mp make_pair
 24 #define st first
 25 #define nd second
 26 #define keyn (root->ch[1]->ch[0])
 27 #define lson (u << 1)
 28 #define rson (u << 1 | 1)
 29 #define pii pair<int, int>
 30 #define pll pair<ll, ll>
 31 #define pb push_back
 32 #define type(x) __typeof(x.begin())
 33 #define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
 34 #define FOR(i, s, t) for(int i = (s); i <= (t); i++)
 35 #define ROF(i, t, s) for(int i = (t); i >= (s); i--)
 36 #define dbg(x) cout << x << endl
 37 #define dbg2(x, y) cout << x << " " << y << endl
 38 #define clr(x, i) memset(x, (i), sizeof(x))
 39 #define maximize(x, y) x = max((x), (y))
 40 #define minimize(x, y) x = min((x), (y))
 41 
 42 inline int readint(){
 43     bool neg = 0; char ch, t[11];
 44     int k = 0;
 45     while((ch = getchar()) == ‘ ‘ || ch == ‘\n‘ || ch == 9) ;
 46     neg = ch == ‘-‘;
 47     ch == ‘-‘ ? neg = 1 : t[k++] = ch;
 48     while((ch = getchar()) >= ‘0‘ && ch <= ‘9‘) t[k++] = ch;
 49     //__ch = ch;
 50     int x = 0, y = 1;
 51     while(k) x += (t[--k] - ‘0‘) * y, y *= 10;
 52     return neg ? -x : x;
 53 }
 54 
 55 inline int readstr(char *s){
 56     char ch;
 57     int len = 0;
 58     while((ch = getchar()) == ‘ ‘ || ch == ‘\n‘ || ch == 9) ;
 59     if(ch == EOF) return 0;
 60     *(s++) = ch, ++len;
 61     while((ch = getchar()) != ‘ ‘ && ch != ‘\n‘ && ch != EOF) *(s++) = ch, ++len;
 62     *s = ‘\0‘;
 63     return len;
 64 }
 65 class cmpt{
 66 public:
 67     bool operator () (const int &x, const int &y) const{
 68         return x > y;
 69     }
 70 };
 71 int Rand(int x, int o){
 72     //if o set, return [1, x], else return [0, x - 1]
 73     if(!x) return 0;
 74     int tem = (int)((double)rand() / RAND_MAX * x) % x;
 75     return o ? tem + 1 : tem;
 76 }
 77 
 78 void data_gen(){
 79     int n = 1e2 + 10;
 80     //freopen("in.txt", "w", stdout);
 81     printf("%d\n", n);
 82     srand(time(0));
 83     FOR(i, 1, n){
 84         int x = Rand(1e5, 0), y = Rand(x, 0) + (x ? Rand(2, 0) : 0), z = Rand(y, 0) + (y ? Rand(2, 0) : 0);
 85         printf("%d %d %d\n", x, y, z);
 86         //solve(x, y, z);
 87     }
 88 }
 89 
 90 struct cmpx{
 91     bool operator () (int x, int y) { return x > y; }
 92 };
 93 int debug = 0;
 94 int dx[] = {-1, 1, 0, 0};
 95 int dy[] = {0, 0, -1, 1};
 96 //-------------------------------------------------------------------------
 97 const int maxn = 5e4 + 10;
 98 const int maxm = maxn << 2;
 99 struct Seg{
100     int l, r, lg, rg;
101     int cnt, length, lazy;
102 }seg[maxm << 2];
103 pair<pii, pii> a[maxn];
104 int n, m, w, h;
105 int buf[maxm], k;
106 map<int, int> mapx, mapy;
107 vector<pii> info[maxm];
108 int anx[maxm], any[maxm];
109 
110 void build(int u, int l, int r, int o){
111     seg[u].l = l, seg[u].r = r;
112     seg[u].lazy = 0;
113     seg[u].length = o ? anx[r] - anx[l] : any[r] - any[l];
114     seg[u].lg = seg[u].rg = seg[u].length;
115     seg[u].cnt = max(0, seg[u].length - m + 1);
116     if(r - l < 2) return;
117     int mid = (l + r) >> 1;
118     build(lson, l, mid, o), build(rson, mid, r, o);
119 }
120 
121 void push_down(int u){
122     seg[lson].lazy += seg[u].lazy, seg[rson].lazy += seg[u].lazy;
123     if(seg[u].lazy < 0){
124         seg[lson].cnt = max(0, seg[lson].length - m + 1);
125         seg[rson].cnt = max(0, seg[rson].length - m + 1);
126         seg[lson].lg = seg[lson].rg = seg[lson].length;
127         seg[rson].lg = seg[rson].rg = seg[rson].length;
128     }else if(seg[u].lazy > 0){
129         seg[lson].cnt = seg[rson].cnt = 0;
130         seg[lson].lg = seg[lson].rg = 0;
131         seg[rson].lg = seg[rson].rg = 0;
132     }
133 }
134 
135 void push_up(int u){
136     int tem = seg[lson].cnt + seg[rson].cnt;
137     tem -= max(0, seg[lson].rg - m + 1);
138     tem -= max(0, seg[rson].lg - m + 1);
139     tem += max(0, seg[lson].rg + seg[rson].lg - m + 1);
140     seg[u].cnt = tem;
141     seg[u].lg = seg[lson].lg + (seg[lson].lg == seg[lson].length ? seg[rson].lg : 0);
142     seg[u].rg = seg[rson].rg + (seg[rson].rg == seg[rson].length ? seg[lson].rg : 0);
143 }
144 
145 void update(int u, int l, int r, int o){
146     if(seg[u].l == l && seg[u].r == r){
147         seg[u].lazy += o;
148         if(o < 0){
149             seg[u].cnt = max(0, seg[u].length - m + 1);
150             seg[u].lg = seg[u].rg = seg[u].length;
151         }else seg[u].cnt = seg[u].lg = seg[u].rg = 0;
152         return;
153     }
154     push_down(u);
155     int mid = (seg[u].l + seg[u].r) >> 1;
156     if(r <= mid) update(lson, l, r, o);
157     else if(l >= mid) update(rson, l, r, o);
158     else update(lson, l, mid, o), update(rson, mid, r, o);
159     push_up(u);
160 }
161 
162 //-------------------------------------------------------------------------
163 int main(){
164     //data_gen(); return 0;
165     //C(); return 0;
166     debug = 0;
167     ///////////////////////////////////////////////////////////////////////////////////////////////////////////////
168     if(debug) freopen("in.txt", "r", stdin);
169     //freopen("out.txt", "w", stdout);
170     while(~scanf("%d", &w)){
171         h = readint(), n = readint(), m = readint();
172         FOR(i, 0, n - 1){
173             int x1 = readint(), y1 = readint(), x2 = readint(), y2 = readint();
174             a[i] = mp(mp(x1, y1), mp(x2, y2));
175         }
176         k = 0;
177         FOR(i, 0, n - 1) buf[k++] = a[i].st.nd, buf[k++] = a[i].nd.nd + 1;
178         buf[k++] = 1, buf[k++] = h + 1;
179         sort(buf, buf + k);
180         k = unique(buf, buf + k) - buf;
181         mapy.clear();
182         FOR(i, 0, k - 1) mapy[buf[i]] = i + 1, any[i + 1] = buf[i];
183         build(1, 1, k, 0);
184         k = 0;
185         FOR(i, 0, n - 1) buf[k++] = a[i].st.st, buf[k++] = a[i].nd.st + 1;
186         buf[k++] = 1, buf[k++] = w + 1;
187         sort(buf, buf + k);
188         k = unique(buf, buf + k) - buf;
189         mapx.clear();
190         FOR(i, 0, k - 1) mapx[buf[i]] = i + 1, anx[i + 1] = buf[i];
191         FOR(i, 1, k) info[i].clear();
192         FOR(i, 0, n - 1) info[mapx[a[i].st.st]].pb(mp(1, i)), info[mapx[a[i].nd.st + 1]].pb(mp(-1, i));
193         ll ans = 0;
194         FOR(i, 1, k - 1){
195             int sz = info[i].size();
196             sort(info[i].begin(), info[i].end());
197             FOR(j, 0, sz - 1){
198                 int lhs = mapy[a[info[i][j].nd].st.nd], rhs = mapy[a[info[i][j].nd].nd.nd + 1];
199                 update(1, lhs, rhs, info[i][j].st);
200             }
201             ans += (ll)(anx[i + 1] - anx[i]) * seg[1].cnt;
202         }
203         build(1, 1, mapx[w + 1], 1);
204         k = mapy[h + 1];
205         FOR(i, 1, k) info[i].clear();
206         FOR(i, 0, n - 1) info[mapy[a[i].st.nd]].pb(mp(1, i)), info[mapy[a[i].nd.nd + 1]].pb(mp(-1, i));
207         FOR(i, 1, k - 1){
208             int sz = info[i].size();
209             sort(info[i].begin(), info[i].end());
210             FOR(j, 0, sz - 1){
211                 int lhs = mapx[a[info[i][j].nd].st.st], rhs = mapx[a[info[i][j].nd].nd.st + 1];
212                 update(1, lhs, rhs, info[i][j].st);
213             }
214             ans += (ll)(any[i + 1] - any[i]) * seg[1].cnt;
215         }
216         if(m == 1) ans >>= 1ll;
217         printf("%lld\n", ans);
218     }
219     //////////////////////////////////////////////////////////////////////////////////////////////////////////////
220     return 0;
221 }